Algorytm sprawdzający, czy język jest pozbawiony kontekstu

Czy istnieje algorytm / systematyczna procedura sprawdzania, czy język jest pozbawiony kontekstu?

Innymi słowy, biorąc pod uwagę język określony w formie algebraicznej (pomyśl o czymś takim jak ), sprawdź, czy język jest pozbawiony kontekstu, czy nie . Wyobraź sobie, że piszemy serwis internetowy, który pomaga uczniom we wszystkich zadaniach domowych; określasz język, a usługa internetowa wyświetla „bez kontekstu” lub „bez kontekstu”. Czy istnieje jakieś dobre podejście do automatyzacji tego? $L=\{a^n b^n a^n : n \in \mathbb{N}\}$

Istnieją oczywiście techniki ręcznego sprawdzania, takie jak lemat pompowania, lemat Ogdena, lemat Parikha, lemat Interchange i inne . Jednak każdy z nich w pewnym momencie wymaga ręcznego wglądu, więc nie jest jasne, jak zmienić którykolwiek z nich w coś algorytmicznego.

Widzę, że Kaveh napisał gdzie indziej, że zestaw języków bezkontekstowych nie jest wymienny rekurencyjnie, więc wydaje się, że nie ma nadziei, że jakiś algorytm zadziała we wszystkich możliwych językach. Dlatego przypuszczam, że usługa internetowa musiałaby być w stanie wyświetlać „bez kontekstu”, „bez kontekstu” lub „nie mogę powiedzieć”. Czy istnieje algorytm, który często byłby w stanie udzielić odpowiedzi innej niż „nie mogę powiedzieć” w wielu językach, które można zobaczyć w podręcznikach? Jak zbudowałbyś taką usługę internetową?

Aby pytanie było dobrze postawione, musimy zdecydować, w jaki sposób użytkownik określi język. Jestem otwarty na sugestie, ale myślę coś takiego:

L. = {mi : S.}

$L = \{E : S\}$

gdzie to wyrażenia słowne, a to system liniowych nierówności względem zmiennych długości, z następującymi definicjami: $E$ $S$

Każda z $x,y,z,\dots$ jest wyrażeniem słownym. (Reprezentują one zmienne, które mogą zawierać dowolne słowo w $\Sigma^*$ .)
Każda z $a,b,c,\dots$ jest wyrażeniem słownym. (Domniemane, $\Sigma=\{a,b,c,\dots\}$ , więc $a,b,c,\dots$ reprezentują pojedynczy symbol w alfabecie.)
Każda z $a^\eta,b^\eta,c^\eta,\dots$ jest wyrażeniem słownym, jeśli $\eta$ jest zmienną długością.
Łączenie wyrażeń słownych jest wyrażeniem słownym.
Każda z jest zmienną długością. (Reprezentują one zmienne, które mogą zawierać dowolną liczbę naturalną). $m,n,p,q,\dots$
Każda z jest zmienną długością. (Reprezentują one długość odpowiadającego słowa.) $|x|,|y|,|z|,\dots$

Wydaje się to wystarczająco szerokie, aby poradzić sobie z wieloma przypadkami, które widzimy w ćwiczeniach z podręczników. Oczywiście, jeśli chcesz, możesz zastąpić dowolną inną tekstową metodę określania języka w formie algebraicznej.

— DW
źródło

Czy nie byłoby łatwiej zacząć od regularności języków?

— Yuval Filmus,

@YuvalFilmus, na pewno! Teraz, kiedy o tym wspominasz, to świetny pomysł. Czy uważasz, że problem jest wykonalny w przypadku zwykłych języków? Z przyjemnością zapytam korespondencję o zwykłe języki, jeśli uważasz, że może to być cenne.

— DW

Z pewnością byłoby łatwiej dla zwykłych języków. Nawiasem mówiąc, ogólna nierozstrzygalność niekoniecznie dotyczy języków wspomnianego formularza.

— Yuval Filmus,

Obawiam się, że ten problem jest prawdopodobnie otwarty, przynajmniej konkretny przypadek to: cstheory.stackexchange.com/questions/17976 . Być może istnieje sposób, aby uzyskać nierozstrzygalność dla bardziej ogólnego problemu, ale nie widzę go.

— sdcvvc

pomocne byłoby podanie przykładowych słów w języku. zasugeruj dalsze badania / współpracę na czacie informatyki

— vzn

Odpowiedzi:

Według twierdzenia Rice'a , czy język zaakceptowany przez maszynę Turinga ma jakąś nietrywialną właściwość (tutaj: brak kontekstu), nie jest rozstrzygalny. Musiałbyś więc ograniczyć moc swojej maszyny rozpoznającej (lub opisu), aby Turing nie był kompletny, mając nadzieję na odpowiedź.

W przypadku niektórych opisów języków odpowiedź jest trywialna: jeśli jest wyrażeniem regularnym, jest regularna, a zatem pozbawiona kontekstu. Jeśli jest to gramatyka bezkontekstowa, to samo.

— vonbrand
źródło

Zgadzam się z wszystkimi twoimi komentarzami, ale nie jestem pewien, czy widzę, jak to odpowiada na pytanie lub jak użyć tego, jak odpowiedzieć na pytanie. Jestem świadomy wszystkich tych faktów. Opisuję konkretny sposób określania języków. Sugerujesz, że jest to ukończenie Turinga? Wydaje mi się, że nie jest to kompletne Turinga. System nierówności liniowych nie jest kompletny według Turinga, więc podejrzewam / spekulowałem, że ograniczyłem go już na tyle, by nie był kompletny według Turinga. Ponadto metoda podana przeze mnie do określania języków nie jest trywialna, ponieważ nie jest wyrażeniem regularnym ani gramatyką bezkontekstową.

— DW

-2

Każdy język jest akceptowany przez Push Down Automata, to CFL. Oto szczegółowy podział, aby ustalić, czy językiem jest CFL, czy nie. sprawdź, czy językiem jest CFL, czy nie

— SiluPanda
źródło

To nie jest algorytm.

— xskxzr,

Nie rozumiem, jak to odpowiada na pytanie. Zdaję sobie sprawę, że język jest pozbawiony kontekstu, i jest akceptowany przez PDA, ale wydaje się, że nie pomaga to w znalezieniu algorytmu formularza wymaganego w pytaniu. Artykuł geeksforgeeks, do którego linkujesz, nie zawiera pełnego algorytmu tego problemu; zawiera tylko niewyczerpujące przypadki specjalne, które są łatwiejsze (i nie jest to świetne odniesienie, ponieważ niektóre z jego wypowiedzi są nieco szkicowe / wątpliwe).

— DW

AFAIK, nie ma jeszcze dobrze ustrukturyzowanego algorytmu. (Popraw mnie, jeśli się mylę). Najlepsze, co możemy zrobić, to sprawdzić przypadki.

— SiluPanda

-3

Wypróbuj oprogramowanie JFLAP, jeśli chcesz tylko sprawdzić CFG. Możesz nawet poprosić programistów JFLAP o podanie kodu lub algorytmu oprogramowania. możesz pobrać JFLAP stąd http://www.jflap.org/jflaptmp/ jest bezpłatny, jednak wymaga JDK lub JRE lub czegoś takiego. A może możesz wypróbować inne podobne oprogramowanie i ich programistów.

— Haseeb Hassan Asif
źródło

Nie jestem pewien, czy to odpowiada na pytanie. JFLAP nie ma funkcji, która akceptuje język w notacji matematycznej i mówi, czy jest on pozbawiony kontekstu, czy nie.

— Yuval Filmus,

TEOREM 2.20 w książce Sipsera Język jest pozbawiony kontekstu, tylko wtedy, gdy rozpozna go jakiś automat z funkcją pushdown. I możesz zbudować PDA w JFLAP z gramatyki

— Haseeb Hassan Asif

Być może masz rację co do zapisu matematycznego, którego nie można umieścić w JFLAP, ale nadal możesz wprowadzić wszystkie reguły gramatyki i może on albo przekształcić go w PDA, albo mówi, że to nie jest CFG lub jakiś inny błąd

— Haseeb Hassan Asif

{a^{n} b^{n} c^{n} : n \in N}

$\{a^nb^nc^n : n \in \mathbb{N}\}$

Wyobrażam sobie, że JFLAP można przekonwertować bezkontekstowych gramatyki do równoważnej PDA, ale to absolutnie nie pomoże tutaj.

— Yuval Filmus,