¿Cómo se demuestra que un lenguaje libre de contexto es ambiguo e indecidible?

He leído en alguna parte que una máquina de Turing no puede calcular esto y, por lo tanto, es indecidible, pero ¿por qué? ¿Por qué es computacionalmente imposible para una máquina generar el árbol de análisis y tomar una decisión? ¿Quizás estoy equivocado y se puede hacer?

Reducimos del problema de correspondencia de Post . Supongamos que podemos, de hecho, decidir el idioma .$\{\langle G\rangle\vert G\textrm{ a CFG and }L(G)\textrm{ ambiguous}\}$

Dado : Construya el siguiente CFG G = ( V , Σ , R , S ) : V = { S , S 1 , S 2 } , R = { S → S 1 | S 2 , S 1 → α 1 $\alpha_1, \ldots, \alpha_m, \beta_1, \ldots, \beta_m$$G = (V,\Sigma,R,S)$$V = \{S, S_1, S_2\}$ (donde σ $R = \{S\rightarrow S_1\vert S_2, S_1\rightarrow \alpha_1 S_1 \sigma_1 \vert \cdots \vert \alpha_m S_1 \sigma_m \vert \alpha_1 \sigma_1 \vert \cdots \vert \alpha_m \sigma_m, S_2\rightarrow \beta_1 S_2 \sigma_1\vert \cdots \vert \beta_m S_2 \sigma_m \vert \beta_1 \sigma_1\vert \cdots \vert \beta_m \sigma_m\}$$\sigma_i$son nuevos caracteres agregados al alfabeto, por ejemplo, ).$\sigma_i = \underline{i}$

Si el lenguaje es ambiguo, entonces hay una derivación de alguna cadena de dos maneras diferentes. Supongamos, wlog, que ambas derivaciones comienzan con la regla S → S 1 , leer los nuevos caracteres hacia atrás hasta que terminan asegura que solo pueda haber una derivación, por lo que no es posible. Por lo tanto, vemos que la única ambigüedad puede provenir de uno de S 1 y uno S 2 'Inicio'. Pero luego, llevando la subcadena de w hasta el comienzo de los nuevos caracteres, tenemos una solución para el PCP (ya que las cadenas de índices utilizadas después de esos puntos coinciden).$w$$S\rightarrow S_1$$S_1$$S_2$$w$

Del mismo modo, si no hay ambigüedad, entonces el PCP no se puede resolver, ya que una solución implicaría una ambigüedad que solo sigue a y S ⇒ S 2 ⇒ ∗ β ˜ σ , donde α = β son cadenas de coincidencias de α 'y β ' s (desde la coincidencia de ˜ σ ).$S\Rightarrow S_1\Rightarrow^* \alpha\tilde{\sigma}$$S\Rightarrow S_2\Rightarrow^* \beta\tilde{\sigma}$$\alpha = \beta$$\alpha$$\beta$$\tilde{\sigma}$

Por lo tanto, hemos reducido a PCP, y como eso es indecidible, hemos terminado.

(¡Avísame si he hecho algo descabellado!)