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:

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.

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.

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

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.