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

19

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?

Ulkmun
la source
1
Oui, vous avez raison, une machine Turing ne peut pas décider si une langue sans contexte est ambiguë ou non, et cela peut être réduit à partir du problème de correspondance postérieure , qui est indécidable. Notez qu'un arbre d'analyse peut être infiniment grand et nous ne pouvons pas décider quand nous arrêterons le calcul.
Hsien-Chih Chang 張顯 之
Hsien-Chih, faites-vous référence à des "arbres d'analyse" pour des mots qui ne sont pas dans la langue (c'est-à-dire des analyses infructueuses), ou essayez-vous de dire que les arbres d'analyse peuvent devenir arbitrairement grands?
Raphael

Réponses:

22

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

Étant donné : Construisez le CFG : , (où sont de nouveaux caractères ajoutés à l'alphabet, par exemple, ).α1,,αm,β1,,βmG=(V,Σ,R,S)V={S,S1,S2}R={SS1|S2,S1α1S1σ1||αmS1σm|α1σ1||αmσm,S2β1S2σ1||βmS2σm|β1σ1||βmσm}σiσi=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).wSS1S1S2w

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 β ˜ σ α = β α β ˜ σSS1ασ~SS2βσ~α=βαβσ~

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!)

alpoge
la source
1
Essayez \ textrm, comme ceci:{GG a CFG and L(G) ambiguous}
Hsien-Chih Chang 張顯 之