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.

fl.formal-languages decidability

— J.-E. Kołek
źródło

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 , tak aby liczba stanów w wzrosła w . Opisujemy CSG pod względem jego zachowania podczas analizowania łańcucha : $D_1, D_2, ...$ $\{1\}$ $D_i$ $i$ $G_X$ $1^n \in \{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 to wyprowadzenie zakończy się niepowodzeniem. Resztę procesu opisujemy w kategoriach obliczeń deterministycznych symulowanych przez jedyne możliwe wyprowadzenie. $n$ $1^n$
Wydrukuj na taśmie kodowanie po którym następuje liczba w systemie binarnym, gdzie i 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 rośnie logarytmicznie w ). $D_i$ $i$ $i = n - c$ $c$ $D_i$ $i$ $i$
Oceń na wejściu . Nie wymaga to reprezentowania taśmy - możesz po prostu zapisać pojedynczy stan, który zmieniasz zgodnie z przejściami miarę zmniejszania . $D_i$ $1^i$ $D_i$ $D_i$ $i$
Jeśli odrzuca , nadpisuj całą taśmę nie-zaciskami, które dają . W przeciwnym razie zawiodę. $D_i$ $1^i$ $1$

Bierzemy . Wyraźnie dla dowolnego , ponieważ . $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 ). $X$ $G_X$

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

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$
Symuluj w przestrzeni między brzegowymi nieterminalami. Jeśli kiedykolwiek przejdzie do jednego ze stanów granicznych, kończymy symulację i zakładamy, że nigdy się nie zatrzymuje. $M$ $M$ $M$
Jeśli postojów, zachowują się jak . 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 nigdy nie będzie w stanie wygenerować łańcucha analizowania, a więc zawiedzie. Jeśli postojów, to istnieje pewna ilość miejsca która wystarcza, że zawiera całą obliczenia „S, w związku analizuje , gdy i , a zatem jest związek i skończony język, skąd $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 jest wyraźnie regularne. $M$ $L(G) = \varnothing$

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

— gdmclellan
źródło

W pierwszej części odpowiedzi

są przykładami jednych kontekstowych nieregularnych języków.

{a^{n^{2}} ∣ n ⩾ 0}

$\{a^{n^2} \mid n \geqslant 0\}$

{a^{p} ∣ p is prime}

$\{a^p \mid \text{$p$ is prime}\}$

— J.-E.

Heh, naprawdę obezwładniony, prawdopodobnie powinienem przyszło mi do głowy, że przekątny argument byłby rażącą przesadą. Chyba zmienię notatkę w odpowiedzi. Mam nadzieję, że druga część była pomocna.

— gdmclellan

@ J.-E.Pin: Nie zastanawiałem się nad tym zbyt często, czy łatwo jest zbudować gramatykę jednoznaczną kontekstową dla

{a^{p} ∣ p is prime}

$\{a^p \mid p \mbox{ is prime}\}$

— Marzio De Biasi,

@ marzio-de-biasi Muszę wyznać, że nie sprawdziłem się, ale polegałem na tej odpowiedzi

— J.-E.

@MarzioDeBiasi Bardzo łatwo. Podczas określania, czy język jest kontekstowy, zwykłym procesem jest coś takiego: 1. niedeterministycznie zgadnij ciąg analizujący; 2. wykonać obliczenia ograniczone spacją, aby ustalić, czy parsowany łańcuch spełnia predykat; i 3. wygenerować ciąg znaków, jeśli stwierdzono, że orzecznik jest spełniony. Problemem może być spacja (ograniczenie przestrzeni jest określane przez długość łańcucha analizującego, ponieważ nie można zawęzić łańcucha pochodnego przy użyciu produkcji kontekstowych), ale w pojedynczym przypadku masz wykładniczą przestrzeń do pracy z .

— gdmclellan

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 , można łatwo skonstruować LBA dla . Zatem wyraźnie jest regularne wtedy i tylko wtedy, gdy 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.

— Georg Zetzsche
źródło

„pustka jest nierozstrzygalna dla jednojęzycznych języków kontekstowych”: czy jest to dobrze znany fakt? Czy miałbyś referencję?

— J.-E.

Biorąc pod uwagę język wrażliwy na kontekst

, weź morfizm

który odwzorowuje każdą literę na

. Wówczas

jest pusty tylko i tylko wtedy, gdy

jest pusty. Dla deterministycznej przestrzeni logicznej, biorąc pod uwagę TM

, można skonstruować det. logspace TM dla zbioru wszystkich

takie, że

ma powstrzymując obliczenia długości

L \subseteq Σ^{*}

$L\subseteq\Sigma^*$

h : Σ^{*} \to {a}^{*}

$h\colon\Sigma^*\to\{a\}^*$

a

$a$

h (L)

$h(L)$

L

$L$

T

$T$

a^{2^{n}}

$a^{2^n}$

T

$T$

n

$n$

— Georg Zetzsche