Comment prouver qu'un langage sans contexte est ambiguë indécidable?

J'ai lu quelque part qu'une machine Turing ne peut pas calculer cela et c'est donc indécidable mais pourquoi? Pourquoi est-il impossible sur le plan informatique pour une machine de générer l'arbre d'analyse et de prendre une décision? Peut-être que je me trompe et que cela peut être fait?

Nous réduisons du problème de correspondance de la poste . Supposons que nous pouvons, en fait, décider de la langue .$\{\langle G\rangle\vert G\textrm{ a CFG and }L(G)\textrm{ ambiguous}\}$

Étant donné : Construisez le CFG : , (où sont de nouveaux caractères ajoutés à l'alphabet, par exemple, ).$\alpha_1, \ldots, \alpha_m, \beta_1, \ldots, \beta_m$$G = (V,\Sigma,R,S)$$V = \{S, S_1, S_2\}$$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$$\sigma_i = \underline{i}$

Si le langage est ambigu, il y a dérivation d'une chaîne de deux manières différentes. En supposant, wlog, que les dérivations commencent toutes les deux par la règle , la lecture des nouveaux caractères en arrière jusqu'à leur fin s'assure qu'il ne peut y avoir qu'une seule dérivation, donc ce n'est pas possible. On voit donc que la seule ambiguïté peut provenir d'un et d'un 'start'. Mais alors, en prenant la sous-chaîne de jusqu'au début des nouveaux caractères, nous avons une solution au PCP (puisque les chaînes d'indices utilisées après ces points correspondent).$w$$S\rightarrow S_1$$S_1$$S_2$$w$

De même, s'il n'y a pas d'ambiguïté, le PCP ne peut pas être résolu, car une solution impliquerait une ambiguïté qui ne fait que suivre et , où sont des chaînes de correspondance de et (depuis la correspondance de ). S ⇒ S 2 ⇒ ∗ β ˜ σ α = β α β ˜ $S\Rightarrow S_1\Rightarrow^* \alpha\tilde{\sigma}$$S\Rightarrow S_2\Rightarrow^* \beta\tilde{\sigma}$$\alpha = \beta$$\alpha$$\beta$$\tilde{\sigma}$

Par conséquent, nous avons réduit le PCP, et comme c'est indécidable, nous avons terminé.

(Faites-moi savoir si j'ai fait quelque chose de stupide!)