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

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?

Wir reduzieren das Korrespondenzproblem von Post . Angenommen, wir können tatsächlich die Sprache .$\{\langle G\rangle\vert G\textrm{ a CFG and }L(G)\textrm{ 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 | ⋯ | $\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}$

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).$w$$S\rightarrow S_1$$S_1$$S_2$$w$

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 ⇒ ∗ β ˜ σ α = β α β ˜ $S\Rightarrow S_1\Rightarrow^* \alpha\tilde{\sigma}$$S\Rightarrow S_2\Rightarrow^* \beta\tilde{\sigma}$$\alpha = \beta$$\alpha$$\beta$$\tilde{\sigma}$

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