Jak udowodnienie, że język bezkontekstowy jest dwuznaczny, nierozstrzygalny?

Czytałem gdzieś, że maszyna Turinga nie może tego obliczyć i dlatego jest nierozstrzygalna, ale dlaczego? Dlaczego komputer nie jest w stanie wygenerować parsowania drzewa i podjąć decyzji? Może się mylę i da się to zrobić?

computability turing-machines context-free

— Ulkmun
źródło

Tak, masz rację, maszyna Turinga nie może zdecydować, czy język bezkontekstowy jest dwuznaczny, czy nie, i można to zmniejszyć dzięki problemowi z korespondencją , który jest nierozstrzygalny. Zauważ, że parsowanie może być nieskończenie duże i nie możemy zdecydować, kiedy zatrzymamy obliczenia.

— Hsien-Chih Chang 張顯之

Hsien-Chih, czy odnosisz się do „drzew parsujących” dla słów nie w języku (tj. Nieudanych parsów), czy też próbujesz powiedzieć, że drzewa parsowania mogą stać się dowolnie duże?

— Raphael

Zmniejszamy problem korespondencji z postem . Załóżmy, że może w istocie zdecydować język . $\{\langle G\rangle\vert G\textrm{ a CFG and }L(G)\textrm{ ambiguous}\}$

Biorąc pod uwagę : Skonstruuj następujące CFG : , $\alpha_1, \ldots, \alpha_m, \beta_1, \ldots, \beta_m$ $G = (V,\Sigma,R,S)$ $V = \{S, S_1, S_2\}$ (gdzie $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$ to nowe znaki dodane do alfabetu, np. ). $\sigma_i = \underline{i}$

Jeśli język jest niejednoznaczny, wówczas istnieje pochodna jakiegoś łańcucha na dwa różne sposoby. Załóżmy, wlog, że oba wyprowadzenia zaczynają się od reguły , czytanie nowych znaków wstecz aż do ich końca upewnia się, że może być tylko jedno wyprowadzenie, więc nie jest to możliwe. Dlatego widzimy, że jedyna dwuznaczność może wynikać z jednego „początku” i jednego . Ale potem, biorąc pod ciąg do początku nowych znaków, mamy rozwiązanie dla PCP (ponieważ ciągi indeksów używane po tych punktach pasują). $w$ $S\rightarrow S_1$ $S_1$ $S_2$ $w$

Podobnie, jeśli nie ma dwuznaczności, wówczas PCP nie można rozwiązać, ponieważ rozwiązanie oznaczałoby dwuznaczność, która następuje po i , gdzie są ciągi pasujące do i (od momentu dopasowania ). $S\Rightarrow S_1\Rightarrow^* \alpha\tilde{\sigma}$ $S\Rightarrow S_2\Rightarrow^* \beta\tilde{\sigma}$ $\alpha = \beta$ $\alpha$ $\beta$ $\tilde{\sigma}$

Dlatego zredukowaliśmy się do PCP, a ponieważ jest to nierozstrzygalne, skończymy.

(Daj mi znać, jeśli zrobiłem coś z głową!)

— alpoge
źródło

Try \textrm, like this:

{⟨ G ⟩ ∣ G a CFG and L (G) ambiguous}

$\{\langle G\rangle \mid G \textrm{ a CFG and } L(G) \textrm{ ambiguous}\}$

— Hsien-Chih Chang 張顯之