Jak intuicyjnie czuć, że język jest regularny

Biorąc pod uwagę język , jak mogę powiedzieć bezpośrednio, nie patrząc na reguły produkcji, że ten język nie jest regularny?$L= \{a^n b^n c^n\}$

Mógłbym użyć lematu pompującego, ale niektórzy mówią tylko patrząc na gramatykę, że to nie jest normalne. Jak to jest możliwe?

Główną właściwością DFA / NFA jest brak nieograniczonej pamięci. Jeśli spojrzysz na język i jedyny algorytm (który później powinien zostać przetłumaczony na automat skończony), który wymyślisz, wymaga tej właściwości, to znaczy czujesz, że każdy algorytm, który go rozpozna, będzie musiał zapamiętać dowolną dużą liczbę rzeczy (lubić$n$ w twoim przykładzie), to prawdopodobnie ten język nie jest regularny.

Oczywiście, zawsze powinieneś pamiętać, że intuicja matematyczna może się mylić, a jedynym sposobem, aby być pewnym swojej intuicji, jest jej udowodnienie.

EDYCJA: Odpowiem na ostatnie pytanie w komentarzach tutaj, z powodu braku miejsca.

mówicie o nieograniczonej pamięci, co masz na myśli to, że nie jest ona regularna. ale ^ nb ^ m może również mieć nieograniczoną pamięć, jeśli chcę, prawda? to wciąż nie daje mi spokoju.

Problem nie polega na tym, jak duże mogą być te słowa (zwykle napotykasz nieskończone regularne języki, ponieważ każdy skończony język jest regularny, a to dość nudne), ale ile DFA musi pamiętać.
w$a^mb^n$ na przykład nie trzeba pamiętać $m,n$. Algorytm musi tylko upewnić się, że są pozytywne i że słowo jest poprawnie uporządkowane. To jest skończona lista, a każdy z elementów na liście wymaga stałej ilości pamięci.
Porównaj to z$a^nb^n$, dla których wymagany jest prosty alogrithm, aby pamiętać, że liczba $a$jest równa liczbie $b$„s. Będzie to wymagało nieograniczonej pamięci. Kiedy patrzę na język i widzę, że każdy algorytm, o którym mogę myśleć, potrzebuje nieograniczonej pamięci, moja intuicja, że ​​język nie jest regularny, staje się silniejsza. Jeśli nie uda mi się znaleźć „inteligentnego” algorytmu (wymagającego stałej ilości pamięci) w rozsądnym czasie (ile rozsądnego czasu zależy od ciebie), spróbuję udowodnić, że język nie jest regularny.
Mam nadzieję, że to czyni to nieco jaśniejszym.

Mógłbym użyć lematu pompującego

Dokładnie. Kiedy użyjesz lematu Pumping lub dowolnej innej techniki kilka (kilkadziesiąt) razy, zaczniesz widzieć wzorce w językach, które zabraniają ich regularności.$a^n\dots b^n$jest bardzo podstawowy, który prawdopodobnie już opanowałeś. Jest to więc kwestia doświadczenia, nie tylko intuicji.

Dobrym sposobem na sprawdzenie intuicji jest spojrzenie na te języki:

1. $\quad \displaystyle \{xyyz \mid x,y,z \in \{a,b\}^+\}$
2. $\quad \displaystyle \{xyyz \mid x,y,z \in \{a,b\}^*\}$
3. $\quad \displaystyle \{xyyz \mid x,y,z \in \{a,b,c\}^+\}$
4. $\quad \displaystyle \{xyyz \mid x,y,z \in \{a,b,c\}^*\}$

Które są pozbawione kontekstu?

Możesz faktycznie zdecydować, czy język jest regularny, używając dość prostych obliczeń, zamiast robić pełny dowód. Musisz po prostu zastosować jedno bardzo silne kryterium: język jest regularny wtedy i tylko wtedy, gdy ma skończenie wiele ilorazów.

Intuicyjnie iloraz jest tym, czego potrzebujesz, aby uzupełnić słowo po przeczytaniu już części danych wejściowych. Bardziej formalnie, lewy iloraz języka$L$ sznurkiem $x$, napisane $x\setminus L$ jest zbiorem ciągów $w$ takie, że $xw \in L$. Na przykład jeśli$L=\{a^nb^n\}$, następnie $a\setminus L= \{a^{n-1} b^n | n\ge 1 \}$, podczas $b \setminus L=\emptyset$. Możemy to łatwo zobaczyć$a^k \setminus L = \{a^{n-k}b^n | n \ge k \}$. Istnieje nieskończenie wiele ilorazów formularza, więc natychmiast po tym następuje$L$ nie jest regularny.

Jeśli zbudujemy DFA $D$ zdecydować L, i $D$ będzie w stanie $S$ po przeczytaniu $a$, następnie $a\setminus L$ jest językiem ustalonym przez $D$ zmodyfikowany tak, aby miał stan początkowy $S$. Ten sam pomysł można wykorzystać do bezpośredniej budowy minimalnego DFA, który decyduje o zwykłym języku na podstawie jego definicji.