Algorytm sprawdzający, czy język jest prawidłowy

Czy istnieje algorytm / systematyczna procedura sprawdzania, czy język jest prawidłowy?

Innymi słowy, biorąc pod uwagę język określony w formie algebraicznej (pomyśl o czymś takim jak $L=\{a^n b^n : n \in \mathbb{N}\}$ ), sprawdź, czy język jest prawidłowy, czy nie. Wyobraź sobie, że piszemy serwis internetowy, który pomaga uczniom we wszystkich zadaniach domowych; użytkownik określa język, a usługa internetowa odpowiada „zwykły”, „nieregularny” lub „nie wiem”. (Chcielibyśmy, aby serwis internetowy odpowiadał „Nie wiem” tak rzadko, jak to możliwe.) Czy istnieje jakieś dobre podejście do automatyzacji? Czy to jest wykonalne? Czy jest to rozstrzygalne (tj. Czy można zagwarantować, że nigdy nie będziemy musieli odpowiadać „nie wiem”)? Czy istnieją rozsądnie wydajne algorytmy do rozwiązania tego problemu i możliwe jest udzielenie odpowiedzi innej niż „nie wiem” dla wielu / większości języków, które mogą powstać w praktyce?

Klasyczną metodą udowodnienia, że język nie jest regularny, jest pompowanie lematu. Wygląda jednak na to, że w pewnym momencie wymaga ręcznego wglądu (np. Wybranie słowa do pompowania), więc nie jestem pewien, czy można go przekształcić w coś algorytmicznego.

Klasyczną metodą udowodnienia, że język jest prawidłowy, byłoby użycie twierdzenia Myhill – Nerode w celu uzyskania automatu stanu skończonego. To wygląda na obiecujące podejście, ale wymaga umiejętności wykonywania podstawowych operacji na językach w formie algebraicznej. Nie jest dla mnie jasne, czy istnieje systematyczny sposób symbolicznego wykonywania wszystkich operacji, które mogą być potrzebne, na językach w formie algebraicznej.

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 = {E : S}

$L = \{E : S\}$

gdzie jest wyrażeniem słownym, a jest systemem liniowych nierówności względem zmiennych długości, z następującymi definicjami: $E$ $S$

Każde z jest wyrażeniem słownym. (Reprezentują one zmienne, które mogą przyjąć dowolne słowo w .) $x,y,z,\dots$ $\Sigma^*$
Każde z jest wyrażeniem słownym. (Tutaj oznacza odwrotność ciągu .) $x^r,y^r,z^r,\dots$ $x^r$ $x$
Każda z liter jest wyrażeniem słownym. (Niejawnie, , więc reprezentują pojedynczy symbol w alfabecie.) $a,b,c,\dots$ $\Sigma=\{a,b,c,\dots\}$ $a,b,c,\dots$
Każdy z to słowo, wyrażenie, jeśli jest długość zmiennej. $a^\eta,b^\eta,c^\eta,\dots$ $\eta$
Łączenie wyrażeń słownych jest wyrażeniem słownym.
Każde z jest zmienną długością. (Reprezentują one zmienne, które mogą przyjmować dowolne liczby naturalne). $m,n,p,q,\dots$
Każdy 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 możesz zastąpić dowolną inną tekstową metodę określania języka w formie algebraicznej, jeśli masz lepszą sugestię.

Nie miałem jeszcze czasu, aby dużo myśleć o twoim wyborze wyrażeń językowych. Z grubsza, jakie języki to obejmuje? Jeśli dodasz ograniczenie, że zmienna słowa występuje tylko raz, czy wszystkie takie języki będą pozbawione kontekstu?

Gilles „SO- przestań być zły”

Może możesz spróbować napisać sam

za pomocą gramatyki? Jak

, czy to zwięźle to, co opisujesz?

E

$E$

E ::= c^{η} ∣ x ∣ E E ∣ E^{r}

$E ::= c^η ∣ x ∣ EE ∣ E^r$

η ::= n ∣ | x |

$η ::= n ∣ |x|$

jmad

Możesz wyrazić

więc wykracza to znacznie poza języki bezkontekstowe. Podejrzewam jednak, że problem jest co najmniej tak trudny, jak decyzja, czy gramatyka bezkontekstowa definiuje zwykły język.

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

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

Gilles „SO- przestań być zły”

@jmad, tak, byłoby to całkowicie rozsądne. Nie jestem przywiązany do tego wyboru wyrażeń językowych: możesz wybrać coś innego, jeśli zobaczysz coś bardziej odpowiedniego. Gilles, świetny kąt ataku! (Dla obserwatorów znane są wyniki pokazujące, że testowanie, czy arbitralna bezkontekstowa gramatyka definiuje zwykły język, jest nierozstrzygalne.) Jeśli problem jest nierozstrzygalny, sugeruję, abyśmy go poprawili, aby usługa internetowa odpowiedziała „Nie „wiem”, a następnie zapytaj o algorytm, który odpowiada „Nie wiem” tak rzadko, jak to możliwe.

Ta klasa nie jest zamknięta pod gwiazdą Kleene, prawda? Czy potrafisz wyrazić zrównoważone nawiasy?

Gilles „SO - przestań być zły”

Odpowiedzi:

Odpowiedź brzmi nie. Decyzja, czy dana gramatyka bezkontekstowa generuje zwykły język, stanowi nierozwiązalny problem.

Aktualizacja . Udzieliłem tej negatywnej odpowiedzi na pytanie ogólne

Biorąc pod uwagę język określony w formie algebraicznej, sprawdź, czy język jest regularny, czy nie

ponieważ języki bezkontekstowe są rozwiązaniami równań algebraicznych w językach: patrz rozdział II, Twierdzenia 1.4 i 1.5 w książce J. Berstela Transductions and Lext-Lext-Languages .

To samo pytanie jest jednak rozstrzygalne w przypadku deterministycznych języków bezkontekstowych, co jest nietypowym wynikiem ze względu na Stearns [1] i ulepszone przez Valiant [2]:
[1] RE Stearns, Test regularności dla maszyn wypychających, informacje i kontrola 11 323- 340 (1967). DOI: 10.1016 / S0019-9958 (67) 90591-8.
[2] LG Valiant. Regularność i związane z nią problemy deterministycznych automatów wypychających J. ACM 22 (1975), s. 1–10.

Jest jeszcze jeden pozytywny wynik, bliższy specyfikacji podanej w drugiej części pytania. Przypomnijmy, że semilinear podzbiory są dokładnie ustawia się zdefiniować arytmetyka presburgera. Istnieją również racjonalne podzbiory . W szczególności, podzbiór określa inequations liniowych racjonalny. Teraz, biorąc pod uwagę racjonalne podzbiór o jest rozstrzygalne czy język $\mathbb{N}^k$ $\mathbb{N}^k$ $\mathbb{N}^k$ $R$ $\mathbb{N}^k$ jest regularne. W istocie, wiadomo, [Ginsburg-Spanier], że jest regularny, jeżeli i tylko jeżeli jest rozpoznawalny podzbiór i jest rozstrzygalne [Ginsburg-Spanier] czy dana racjonalne podzbiór jest rozpoznawalny.

L. (R) = {u_{1}^{n_{1}} \dots u_{k}^{n_{k}} ∣ (n_{1}, . . ., n_{k}) \in R}

$L(R) = \{ u_1^{n_1} \dotsm u_k^{n_k} \mid (n_1, ...,n_k) \in R \}$

L (R)

$L(R)$

R

$R$

N^{k}

$\mathbb{N}^k$

N^{k}

$\mathbb{N}^k$

S. Ginsburg i EH Spanier., Półgrupy, formuły Presburger i języki , Pacific J. Math. 16 (1966) 285–296.

S. Ginsburg i EH Spanier. Ograniczone zestawy regularne , Proc. amerykańskiej matematyki. Soc. 17 , 1043–1049 (1966).

To nie rozwiązuje drugiej części pytania, która może być nierozstrzygalna z powodu zmiennych słów, ale daje rozsądny fragment na początek.

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

(a) Pedantyczny nit: Nie jest dla mnie jasne, czy powyższa składnia algebraiczna jest wystarczająco ogólna, aby wyrazić wszystkie gramatyki bezkontekstowe (jak wskazaliśmy w komentarzach Gillesa), więc nie jest całkiem jasne, czy ten konkretny wynik ma zastosowanie tutaj . (b) Co ważniejsze: rozważ poprawność opisu problemu, aby usługa internetowa mogła odpowiedzieć „nie wiem” i chcielibyśmy znaleźć algorytm, który odpowiada „nie wiem” tak rzadko jak to możliwe. Wcześniej sugerowałem to w komentarzach; Przeredaguję pytanie, aby było jaśniejsze w samym pytaniu.

Podejrzewam, że możesz dostosować dowód, ale wynik nie następuje. Myślę, że istnieją języki bezkontekstowe, których nie można wyrazić w tym formalizmie: na przykład, jak wyrażać zrównoważone nawiasy? Klasa języków nie jest zamknięta pod gwiazdą Kleene, prawda?

Gilles „SO- przestań być zły”

@Gilles, tak, myślałem o tym. Nie od razu wiadomo mi, jak dostosować dowód. Standardowy dowód, że nierozstrzygalne jest stwierdzenie, czy gramatyka bezkontekstowa jest regularna, opiera się na twierdzeniu Greibacha. Nie wydaje mi się jednak, aby ta klasa języków spełniała założenia twierdzenia Greibacha (nie wydaje się prawdopodobne, aby był zamknięty w wyniku konkatenacji z regularnymi zbiorami i zamknięty w ramach unii). Może jest jakieś inne podejście dowodowe, którego nie znam. Zgadzam się, nie jest jasne, jak wyrazić język zrównoważonych nawiasów w tej algebraicznej formie.

Właśnie dodałem referencje.

J.-E.

Twój post nie odpowiada na pytanie, ponieważ dotyczy innej klasy języków. Dopuszczalne tutaj formy algebraiczne (z jednym wyrażeniem słownym) nie są (o ile możemy powiedzieć) tak ogólne, jak formy algebraiczne potrzebne do wyrażania dowolnych języków bezkontekstowych. Może się zdarzyć, że w przypadku przecięcia tych dwóch problemów problem będzie rozstrzygalny.

Gilles 'SO - przestań być zły'