Wie lässt sich beweisen, dass eine kontextfreie Sprache nicht eindeutig zu entscheiden ist?

19

Ich habe irgendwo gelesen, dass eine Turing-Maschine dies nicht berechnen kann und es daher unentscheidbar ist, aber warum? Warum ist es einer Maschine rechnerisch unmöglich, die Analysebäume zu generieren und eine Entscheidung zu treffen? Vielleicht irre ich mich und es kann getan werden?

Ulkmun
quelle
1
Ja, Sie haben Recht, eine Turing-Maschine kann nicht entscheiden, ob eine kontextfreie Sprache mehrdeutig ist oder nicht, und dies kann durch das Post-Korrespondenz-Problem , das nicht zu entscheiden ist, verringert werden . Beachten Sie, dass ein Analysebaum unendlich groß sein kann und wir nicht entscheiden können, wann wir die Berechnung stoppen.
Hsien-Chih Chang 張顯 張顯
Hsien-Chih, beziehen Sie sich auf "Analysebäume" für Wörter, die nicht in der Sprache sind (dh nicht erfolgreiche Analyse), oder versuchen Sie zu sagen, dass Analysebäume beliebig groß werden können?
Raphael

Antworten:

22

Wir reduzieren das Korrespondenzproblem von Post . Angenommen, wir können tatsächlich die Sprache .{G|G a CFG and L(G) ambiguous}

Gegebene : Konstruiere die folgende CFG : , (wobei neue Zeichen sind, die dem Alphabet hinzugefügt wurden, z. B. ). G = ( V , Σ , R , S ) V = { S , S 1 , S 2 } R = { S S 1 | S 2 , S 1α 1 S 1 σ 1 | | αα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_

Wenn die Sprache mehrdeutig ist, gibt es eine Ableitung einer Zeichenfolge auf zwei verschiedene Arten. Angenommen, wlog, die Ableitungen beginnen beide mit der Regel und lesen die neuen Zeichen rückwärts, bis sie enden, um sicherzustellen, dass es nur eine Ableitung geben kann. Das ist also nicht möglich. Wir sehen also, dass die einzige Mehrdeutigkeit von einem und einem -Start ausgehen kann. Wenn wir jedoch die Teilzeichenfolge von bis zum Anfang der neuen Zeichen nehmen, haben wir eine Lösung für die PCP (da die nach diesen Punkten verwendeten Indexzeichenfolgen übereinstimmen).wSS1S1S2w

In ähnlicher Weise kann der PCP nicht gelöst werden, wenn keine Mehrdeutigkeit vorliegt, da eine Lösung eine Mehrdeutigkeit implizieren würde, die gerade auf und folgt. , wobei Zeichenfolgen von übereinstimmenden 's und ' s sind (seit der Übereinstimmung von ). S S 2 β ˜ σ α = β α β ˜ σSS1ασ~SS2βσ~α=βαβσ~

Daher haben wir uns auf PCP reduziert, und da dies nicht zu entscheiden ist, sind wir fertig.

(Lass es mich wissen, wenn ich etwas ohne Kopf getan habe!)

alpoge
quelle
1
Probieren Sie \ textrm wie folgt aus:{GG a CFG and L(G) ambiguous}
Hsien-Chih Chang 張顯 張顯