Decydowanie, czy jednolity język kontekstowy jest prawidłowy

To dobrze znany wynik, że pytanie

Czy gramatyka bezkontekstowa generuje zwykły język?

jest nierozstrzygalny. Jednak staje się to rozstrzygalne na podstawie jednoznacznego alfabetu, po prostu dlatego, że w tym przypadku klasy języków bezkontekstowych i zwykłych pokrywają się.

Moje pytanie polega na tym, aby wiedzieć, co dzieje się w przypadku jednoargumentowych języków kontekstowych .

Czy można rozstrzygnąć, czy dana gramatyka kontekstowa na jednoargumentowym alfabecie generuje zwykły język.

Jeśli odpowiedź jest pozytywna, mile widziane byłoby oszacowanie złożoności.

Niestety, twój problem jest nierozstrzygalny. Podejście, na które natknąłem się (które może być obezwładnione, więc każdy, kto ma bardziej celowe podejście, powinno się wzmocnić!) Najpierw używa przekątnego argumentu, aby wykazać, że istnieje jednolity CSL $X$ który nie jest regularny (w przeciwieństwie do wyniku pozytywnego dla jednorzędowych świetlówek kompaktowych), a następnie zmniejsza problem zatrzymania maszyn Turinga, biorąc pod uwagę TM $M$ , konstruując CSG $G$ który symuluje $M$ na długości taśmy krótszej niż łańcuch parsowania $w$ , rozpoznając $X$ jeśli $M$ zatrzymuje się bez przekraczania swoich granic i nie parsuje inaczej, tak aby $G$ powodzeniem analizował wszystkie $w \in X$które są wystarczająco długie iff $M$ zatrzymuje (tak, że $L(G)$ różni się od $X$ tylko skończoną liczbą łańcuchów i dlatego nie może być regularny), w przeciwnym razie $G$ rozpozna pusty język (który jest wyraźnie regularny).

Kluczem do tego podejścia jest obserwacja, że ​​CSG nie zajmują się jedynie kwestiami gramatycznymi, takimi jak struktura fraz - w rzeczywistości sekwencje wyprowadzania CSG mogą przeprowadzać dowolne niedeterministyczne obliczenia ograniczone przestrzenią (rzeczywiście istnieją $\mathbf{PSPACE}$-kompletne CSL), zanim przejdziemy do wyrównywania z ciągiem analizy. Najłatwiej to zaobserwować poprzez standardowe konwersje między CSG i gramatykami monotonicznymi (które nadal działają, gdy są ograniczone do jednoargumentowych alfabetów), oraz zastosowanie prostych monotonicznych produkcji do symulacji przejść maszyny Turinga na łańcuchach pochodnych, które reprezentują etapy w historii obliczeń. W tej odpowiedzi założę, że czytelnik może zrozumieć większość szczegółów, gdy CSG jest wymagany do symulacji danego obliczenia. (Zakładam, że pytający czuje się dobrze z tym wszystkim, ale zastanawiam się nad tym, czy jest kompletny. Niemniej jednak prosimy o wyjaśnienia w komentarzach).

Po pierwsze, potrzebujemy naszego nieregularnego jednoargumentowego CSG. ( EDYCJA: więc to była przesada - nieregularne, jednoargumentowe CSL można łatwo wykazać np. Poprzez pompowanie lematu w dowolnym języku, który wykazuje najbardziej podstawową nieregularność. Patrz komentarze dla przykładów. Z perspektywy czasu, używając przekątnego argumentu było jak przyłożenie głowicy nuklearnej do walki na noże. Przejrzyj tę konstrukcję, jeśli jesteś ciekawy, w przeciwnym razie przejdź do redukcji).

Niech być wyliczeniem DFA nad alfabetem { 1 } , tak aby liczba stanów w D i wzrosła w i . Opisujemy CSG G X pod względem jego zachowania podczas analizowania łańcucha 1 n ∈ { 1 } ∗ :$D_1, D_2, ...$$\{1\}$$D_i$$i$$G_X$$1^n \in \{1\}^*$

1. Niedeterministycznie generuje ciąg „pustych” nieterminali, które uważamy za „taśmę”. Jeden z pustych nieterminali powinien być osobnym „nieokreślonym„ pustym + głowicą do odczytu i zapisu + początkowego stanu ”. Jeśli parsowany ciąg nie jest równy 1 n, to wyprowadzenie zakończy się niepowodzeniem. Resztę procesu opisujemy w kategoriach obliczeń deterministycznych symulowanych przez jedyne możliwe wyprowadzenie.$n$$1^n$
2. Wydrukuj na taśmie kodowanie po którym następuje liczba i w systemie binarnym, gdzie i = n - c i c jest wybierane, aby zawsze mieć wystarczająco dużo miejsca na taśmie, aby zrobić to, co musimy. (Jest to możliwe, ponieważ wymagana przestrzeń do kodować ď I i I rośnie logarytmicznie w I ).$D_i$$i$$i = n - c$$c$$D_i$$i$$i$
3. Oceń na wejściu 1 i . Nie wymaga to reprezentowania taśmy D i - możesz po prostu zapisać pojedynczy stan, który zmieniasz zgodnie z przejściami D i w miarę zmniejszania i .$D_i$$1^i$$D_i$$D_i$$i$
4. Jeśli odrzuca 1 i , nadpisuj całą taśmę nie-zaciskami, które dają 1 . W przeciwnym razie zawiodę.$D_i$ $1^i$$1$

Bierzemy . Wyraźnie X ≠ L ( D i ) dla dowolnego i , ponieważ 1 i + c ∈ X ⇔ 1 i + c ∉ L ( D i ) .$X = L(G_X)$$X \ne L(D_i)$$i$$1^{i+c} \in X \Leftrightarrow 1^{i+c} \notin L(D_i)$

Następnym krokiem jest zaprojektowanie redukcji z problemu zatrzymania do problemu osoby pytającej. (Jeśli pominąłeś powyższą sekcję, niech będzie arbitralnym niestandardowym nieliniowym CSL generowanym przez CSG G X ).$X$$G_X$

Niech będzie arbitralną TM. Konwertujemy M na CSG G, który zachowuje się w następujący sposób przy analizie ciągu 1 n :$M$$M$$G$$1^n$

1. Wygeneruj puste nieterminale, przy czym najbardziej lewy to osobny blank + głowica do odczytu i zapisu nieterminalny, a także wygeneruj „graniczny” nieterminalny z każdej strony. Ponownie, jeśli wygenerujemy niewłaściwą liczbę nieterminali, wówczas ponosimy porażkę.$n-2$
2. Symuluj w przestrzeni między brzegowymi nieterminalami. Jeśli M kiedykolwiek przejdzie do jednego ze stanów granicznych, kończymy symulację i zakładamy, że M nigdy się nie zatrzymuje.$M$$M$$M$
3. Jeśli postojów, zachowują się jak G- X . Gdybyśmy musieli zakończyć symulację, to nie powiodła się.$M$$G_X$

Zauważ, że jeśli zdoła działać wiecznie w granicach, to G nigdy nie będzie w stanie wygenerować łańcucha analizowania, a więc zawiedzie. Jeśli M postojów, to istnieje pewna ilość miejsca N która wystarcza, że zawiera m całą obliczenia „S, w związku G analizuje 1 m , gdy m ≥ n + 2 i 1 m ∈ X , a zatem X jest związek L ( G ) i skończony język, skąd L ( G $M$$G$$M$$n$$M$$G$$1^m$$m \ge n+2$$1^m \in X$$X$$L(G)$$L(G)$nie jest regularny. Z drugiej strony, jeśli nigdy się nie zatrzymuje, to L ( G ) = ∅ jest wyraźnie regularne.$M$$L(G) = \varnothing$

Algorytm decydujący, czy jest regularny, czy nie, określa, czy M zatrzymuje się na czystej taśmie, co jest nierozstrzygalne. Wynika z tego, że problem osoby pytającej jest nierozstrzygalny.$L(G)$$M$

Jest to zasadniczo ta sama odpowiedź, co powyżej, ale ponieważ poszukiwana jest odpowiedź „bardziej celowa”, wspominam o tym: (Jest to również mój pierwszy post tutaj, więc wybacz mi, jeśli zamieszczam trywialność!)

Zauważ, że pustka jest nierozstrzygalna dla jednojęzycznych języków kontekstowych. Napraw kontekstowy, ale nieregularny język . Biorąc pod uwagę LBA dla L ⊆ a ∗ , można łatwo skonstruować LBA dla L ′ = { a n ∣ a n ∈ N  i  ∃ m ≤ n : a m ∈ L } . Zatem wyraźnie L ' jest regularne wtedy i tylko wtedy, gdy L jest pusty.$N\subseteq a^*$$L\subseteq a^*$$L'=\{ a^n \mid \text{$a^n\in N$ and $\exists m\le n\colon a^m \in L$}\}$$L'$$L$

Aktualizacja: Oczywiście ten sam argument pokazuje, że nierozstrzygalność obowiązuje już dla deterministycznej przestrzeni logarytmicznej.