Jak udowodnić, że język nie jest regularny?

Dowiedzieliśmy się o klasie języków zwykłych . Charakteryzuje go dowolna koncepcja wśród wyrażeń regularnych, automatów skończonych i gramatyk lewostronnych, więc łatwo jest wykazać, że dany język jest regularny.$\mathrm{REG}$

Jak jednak pokazać coś przeciwnego? Moja TA była nieugięta, że ​​aby to zrobić, musielibyśmy wykazać dla wszystkich wyrażeń regularnych (lub dla wszystkich automatów skończonych lub dla wszystkich gramatyk lewostronnych), że nie potrafią opisać języka, który jest pod ręką. To wydaje się dużym zadaniem!

Czytałem o lemie pompującym, ale wygląda to na bardzo skomplikowane.

^{To ma być pytanie referencyjne gromadzące zwykłe metody dowodowe i przykłady zastosowań. Zobacz tutaj to samo pytanie dotyczące języków bezkontekstowych.}

Dowód sprzeczności jest często używany do wykazania, że ​​język nie jest regularny: niech jest właściwością prawdziwą dla wszystkich zwykłych języków, jeśli twój konkretny język nie weryfikuje , to nie jest on regularny. Można użyć następujących właściwości:$P$$P$

1. Tłoczący się lemat, czego przykładem jest odpowiedź Dave'a ;
2. Właściwości zamknięcia zwykłych języków (operacje na zestawach, konkatenacja, gwiazda Kleene, lustro, homomorfizmy);
3. Zwykły język ma skończoną liczbę klas równoważności prefiksów, twierdzenie Myhill – Nerode .

Aby udowodnić, że język nie jest regularny przy użyciu właściwości zamknięcia, technika polega na połączeniu języka L ze zwykłymi językami za pomocą operacji, które zachowują prawidłowość w celu uzyskania języka znanego jako nieregularny, np. Język archetypiczny I = { a n b n | n ∈ N } . Na przykład, niech L = { a p b q | p ≠ q } . Załóżmy, że L jest regularny, ponieważ zwykłe języki są zamknięte pod uzupełnieniem, podobnie jak L jest uzupełnieniem $L$$L$$I= \{ a^n b^n | n \in \mathbb{N} \}$$L= \{a^p b^q | p \neq q \}$$L$$L$ . Teraz podjąć przecięcie L C i do ⋆ b ⋆ który jest regularny, otrzymujemy ja , który nie jest regularny.$L^c$$L^c$$a^\star b^\star$$I$

Twierdzenie Myhill – Nerode można wykorzystać do udowodnienia, że ​​nie regularny. Dla p ≥ 0 , I / P = { R b R b p | R ∈ N } = I . { b p } . Wszystkie klasy są różne i istnieje policzalna nieskończoność takich klas. Ponieważ zwykły język musi mieć skończoną liczbę zajęć , nie jestem regularny.$I$$p \geq 0$$I/a^p= \{ a^{r}b^rb^p| r \in \mathbb{N} \}=I.\{b^p\}$$I$

W oparciu o odpowiedź Dave'a, oto „instrukcja” krok po kroku jak używać lematu pompującego.

Przypomnijmy sobie pompujący lemat (wzięty z odpowiedzi Dave'a, wzięty z Wikipedii):

Niech $L$ będzie zwykłym językiem. Następnie istnieje liczba całkowita $n\ge 1$ (w zależności tylko $L$ ) taką, że każdy łańcuch $w$ w $L$ o długości co najmniej $n$ ( $n$ jest nazywany „długość pompowania”) może być zapisane jako $w = xyz$ (to jest $w$ puszce podzielić na trzy podciągi), spełniając następujące warunki:

1. $|y| \ge 1$
2. $|xy| \le n$ i
3. Określenie "pompowana" $w$ jeszcze w $L$ wszystka $i \ge 0$ , $xy^iz \in L$ .

Załóżmy, że znasz język $L$ i chcesz pokazać, że nie jest on regularny poprzez lemat pompowania. Dowód wygląda następująco:

1. Załóżmy, że $L$ jest regularne.
2. Jeśli jest regularny, to lemat pompowania mówi, że istnieje pewna liczba $n$ która jest długością pompowania.
3. Wybierz konkretne słowo $w\in L$ o długości większej niż $n$ . Trudność polega na tym, aby wiedzieć, które słowo wybrać.
4. Rozważ WSZYSTKIE sposoby podzielenia $w$ na 3 części, $w=xyz$ , za pomocą $|xy|\le n$ i $y$ niepuste. Dla każdego z tych sposobów, pokazują, że nie mogą być pompowane: istnieje zawsze pewne $i\ge 0$ taka, że $xy^iz \notin L$ .
5. Wniosek: słowa $w$ nie można „pompować” (bez względu na to, jak podzielimy je na $xyz$ ) w przeciwieństwie do lematu pompowania, tzn. Nasze założenie (krok 1) jest błędne: $L$ nie jest regularne.

Zanim przejdziemy do przykładu, powtórzę krok 3 i krok 4 (w tym miejscu większość ludzi się myli). W punkcie 3 należy wybrać jeden konkretny wyraz w $L$ . zapisz to wprost, np. „00001111” lub „ $a^nb^n$ ”. Przykłady rzeczy, które nie są konkretnym słowem: „ $w$ ” lub „słowo, które ma 000 jako przedrostek”.

Z drugiej strony w kroku 4 należy rozważyć więcej niż jedną sprawę. Na przykład, jeśli $w=000111$ nie wystarczy powiedzieć $x=00, y=01, z=00$ , a następnie dojść do sprzeczności. Musisz również sprawdzić $x=0, y=0, z=0111$ i $x=\epsilon, y=000, z=111$ i wszystkie inne możliwe opcje.

Teraz wykonajmy następujące kroki i udowodnij, że $L= \{ 0^k1^{2k} \mid k>0 \}$ nie jest regularne.

1. Załóżmy, że $L$ jest regularny.
2. Niech $n$ będzie długością pompowania podaną przez lemat pompowania.
3. Niech $w = 0^n 1^{2n}$ .
   (kontrola poczytalności: $|w|\gt n$ w razie potrzeby. Dlaczego to słowo? inne słowa też mogą działać .. potrzeba trochę doświadczenia, aby znaleźć właściwe $w$ ). Ponownie zwróć uwagę, że $w$ jest specyficznym słowem: $\underbrace{000\ldots0}_{n \text{ times}}\underbrace{111\ldots1}_{2n \text{ times}}$ .
4. Teraz zacznijmy rozważać różne przypadki podzielenia $w$ na $xyz$ pomocą $|xy|\le n$ oraz $|y|>0$ . Ponieważ $|xy|<n$ bez względu na to, jak podzielimy $w$ , $x$ będzie składać się tylko z zer, a więc $y$ . Załóżmy $|x|=s$ i $|y|=k$ . Musimy rozważyć WSZYSTKIE opcje, czyli wszystkie możliwe $s,k$ takie, że$s\ge 0, k\ge 1$ oraz$s+k \le n$ . W TYM$L$ dowód na wszystkie te przypadki jest taki sam, ale ogólnie może być inny.
   weź$i=0$ i rozważ$xy^iz = xz$ . to słowo NIE jest w$L$ ponieważ ma postać$0^{n-k}1^{2n}$ (bez względu na$s$ i$k$były), a ponieważ $k \ge 1$ , tego słowa nie ma w $L$ i dochodzimy do sprzeczności.
5. Zatem nasze założenie jest błędne, a $L$ nie jest regularne.

Klip youtube, który wyjaśnia, jak używać lematu pompującego według tych samych linii, można znaleźć tutaj

Z Wikipedii język pompowania dla zwykłych języków jest następujący:

Niech będzie zwykłym językiem. Następnie istnieje całkowita P ≥ 1 (w zależności tylko L ) taką, że każdy łańcuch wagowych w L o długości co najmniej p ( p nazywany jest „długość pompowania”) może być zapisane jako W = x y Z (czyli w puszce podzielić na trzy podciągi), spełniając następujące warunki:$L$$p\ge 1$$L$$w$$L$$p$$p$$w = xyz$$w$

1. $|y| \ge 1$
2. i $|xy| \le p$
3. dla wszystkich , x y i z ∈ l . y jest podciągiem, który można pompować (usuwać lub powtarzać dowolną liczbę razy, a wynikowy ciąg jest zawsze w L ). $i \ge 0$$xy^iz \in L$
   $y$$L$

(1) oznacza, że ​​pętla y, która ma być pompowana, musi mieć co najmniej jedną długość; (2) oznacza, że ​​pętla musi wystąpić w obrębie pierwszych p znaków. Nie ma ograniczeń dla xiz.

W prostych słowach: Dla każdego języka regularnego L każde wystarczająco długie słowo można podzielić na 3 części. tj W = X Y z , tak, że wszystkie struny x y k oo o k ≥ 0 jest także L .$w\in L$$w = xyz$$xy^kz$$k\ge 0$$L$

Rozważmy teraz przykład . Niech .$L=\{(01)^n2^n\mid n\ge0\}$

Aby pokazać, że nie jest to regularne, należy rozważyć, jak wyglądają wszystkie dekompozycje , więc jakie są wszystkie możliwe rzeczy x, y i z, że x y z = ( 01 ) p 2 p (decydujemy się przyjrzeć temu słowu o długości 3 p , gdzie p jest długością pompowania). Musimy rozważyć, gdzie występuje część y ciągu. Może pokrywać się z pierwszą częścią, a zatem będzie równa albo ( 01 ) k + 1 , ( 10 $w=xyz$$xyz=(01)^p2^p$$3p$$p$$y$$(01)^{k+1}$ ,1(01 ) k lub0(10 ) k , dla niektórychk≥0(nie zapomnij, że | y | ≥1). Może się pokrywać z drugą częścią, co oznacza, żey= 2 k , dla niektórychk>0. Lub może nakładać się na dwie części słowa i będzie mieć postać(01 ) k + 1 2 l ,(10 ) $(10)^{k+1}$$1(01)^k$$0(10)^k$$k\ge 0$$|y|\ge 1$$y=2^k$$k>0$$(01)^{k+1} 2^l$ ,1(01 ) k 2 l lub0(10 ) k 2 l , dlak≥0il≥1.$(10)^{k+1} 2^l$$1(01)^k 2^l$$0(10)^k 2^l$$k\ge0$$l\ge1$

Teraz pompuj każdy, aby uzyskać sprzeczność, która będzie słowem nie w twoim języku. Na przykład, jeśli weźmiemy , lemat pompowania mówi na przykład, że x y 2 z = x 0 ( 10 ) k 2 l 0 ( 10 ) k 2 l z musi znajdować się w język, przez odpowiedni dobór X i z . Ale to słowo nie może być w języku, ponieważ 2 pojawia się przed 1 .$y=0(10)^k2^l$$xy^2z=x0(10)^k2^l0(10)^k2^lz$$x$$z$$2$$1$

Inne przypadki spowodują, że liczba będzie większa niż liczba 2 lub odwrotnie, lub spowoduje, że słowa, które nie będą miały struktury ( 01 ) n 2 n , na przykład przez dwa zera z rzędu.$(01)$$2$$(01)^n2^n$$0$

Nie zapominaj, że . Przydatne jest tutaj skrócenie dowodu: wiele powyższych rozkładów jest niemożliwych, ponieważ spowodowałyby, że część Z byłaby zbyt długa.$|xy| \le p$$z$

Każdy z powyższych przypadków musi prowadzić do takiej sprzeczności, która byłaby wówczas sprzecznością z pompującym lematem. Voila! Język nie byłby regularny.

Dla danego języka pozwól$L \subseteq \Sigma^*$

$\qquad \displaystyle S_L(z) = \sum\limits_{n \geq 0} |L \cap \Sigma^n|\cdot z^n$

The (zwykłe) generowania funkcji z , czyli jego sekwencję liczbę słów na długości.$L$

Następująca instrukcja zawiera [ FlSe09 , p52]:

$\qquad \displaystyle L \in \mathrm{REG} \quad \Longrightarrow \quad S_L \text{ rational}$

Oznacza to, że zwielomianamiP,$S_L(z) = \frac{P(z)}{Q(z)}$$P,Q$

$S_L$

Przykład: Weź pod uwagę język poprawnie zagnieżdżonych nawiasów, tj . Język Dyck . Jest generowany przez jednoznaczną gramatykę

$\qquad \displaystyle S \to [S]S \mid \varepsilon$

co można przełożyć na równanie

$\qquad \displaystyle S(z) = z^2S^2(z) + 1$

jednym rozwiązaniem (tym ze wszystkimi dodatnimi współczynnikami) jest

$\qquad \displaystyle \mathcal{S}(z) = \frac{1 - \sqrt{1 - 4z^2}}{2z^2}$

$S_L = \mathcal{S}$$\mathcal{S}$

1. Dowód stwierdzenia dla zwykłych języków działa przez gramatykę i natychmiast przenosi do gramatyki liniowej (przemienność mnożenia).

$\ \ $[FlSe09] Analytic Combinatorics autorstwa P. Flajolet i R. Sedgewick (2009) [Kuic70] O entropii języków bezkontekstowych W. Kuich (1970)
$\ \ $

$L = \{(01)^m 2^m \mid m \ge0\}$

Myślisz, że pompowanie lematu wygląda na skomplikowane? Nie martw się Oto nieco inne podejście, ukryte również w odpowiedzi @ Romualda. (Quiz: gdzie?)

Zacznijmy od przypomnienia, że ​​każdy język regularny jest akceptowany przez deterministyczny automat skończony (DFA). DFA to skończony wykres, w którym każdy wierzchołek ma dokładnie jedną krawędź na każdą literę alfabetu. Ciągi umożliwiają przejście na wykresie opartym na wierzchołku oznaczonym „początek”, a DFA akceptuje, jeśli ten spacer kończy się na wierzchołku oznaczonym „zaakceptuj”. (Wierzchołki nazywane są „stanami”, ponieważ różne obszary matematyki lubią tworzyć własną terminologię dla tego samego.)

$a$$b$$c$$ac$$bc$

$L$$a$$b$$c$$ac$$bc$$L$

$a$$b$$c$$ac$$bc$$m$$\{(01)^i : 0\le i\le m+1\}$$a=(01)^p$$b=(01)^q$$p\neq q$$a2^p$$b2^p$

Zaletą jest to, że przykład jest tak naprawdę szablonem do udowodnienia, że ​​języki nie są regularne:

• $\{a_i :i\in\mathbb{N}\}$$t_i$$a_it_i$$a_it_j$$i\neq j$
• $a_i$

Istnieją inne sztuczki, ale ta z łatwością sprawdzi się w przypadku większości problemów domowych.

Edycja: Wcześniejsza wersja omawiała, w jaki sposób ten pomysł odnosi się do Pumping Lemma.

Po odpowiedzi tutaj opiszę metodę udowodnienia nieregularności opartą na złożoności Kołmogorwa.

Podejście to omówiono w „Nowym podejściu do formalnej teorii języka przez złożoność Kołmogorowa” , autorstwa Ming Li i Paula MB Vitanyi (patrz sekcja 3.1).

$K(x)$$x$$M$$M(\epsilon)=x$

$L\subseteq \Sigma^*$$c$$L$$x\in\Sigma^*$$y$$n'th$$L_x=\left\{y\in \Sigma^*|xy\in L\right\}$$K(y)\le O(\log n)+c$

$x\in\Sigma^*$$n'th$$L_x$

• $L$
• $x$
• $n$

$x$$x$$L$$n$$\log n$$y$

$L_x$$L$$x\in\Sigma^*$$L$

$L=\left\{1^p | \text{p is prime}\right\}$$L=\left\{0^n1^n| n\ge 0\right\}$

$x\in\left\{0,1\right\}^*$$y_i^x$$i'th$$L_x$$y_1^{0^i}=1^i$$x$$x=0^i$$n=1$$\forall i\ge 0 : K(y_1^{0^i})\le c$$y_1^{0^i}=1^i$$1^i$$x$$x=0^n$$n$$K(0^n)\ge \log n$$y_1^x=1^n$$K(1^n)<c$$n>2^c$

$\{ \sigma \}$$A \subseteq \mathbb{N}$

$A \subseteq \mathbb{N}$

1. $L(A)$

2. $L(A)$

3. $n_0,m \geq 1$$n \geq n_0$$n \in A$$n+m \in A$$A$

4. $a_i = 1_{i \in A}$$0.a_0a_1a_2\ldots$

5. $\sum_{i \in A} x^i$

$\rho$$\rho$

$A \subseteq \mathbb{N}$$L(A)$

1. $\rho = \lim_{n\to\infty} \frac{|A \cap \{1,\ldots,n\}|}{n}$$A$

2. Jeśli to jest skończone.$\rho = 0$$A$

3. Jeśli to jest cofinite (to znaczy jest skończone).A ¯ $\rho = 1$$A$$\overline{A}$

Na przykład język nie jest regularny, ponieważ zbiór ma zanikającą gęstość asymptotyczną, ale jest nieskończony.$L(\{2^n : n \geq 0\})$

Klasa języków zwykłych jest zamykana w ramach różnych operacji zamykania, takich jak łączenie, przecinanie, uzupełnianie, homomorfizm, regularne podstawianie, odwrotny homomorfizm i inne. Można to wykorzystać do udowodnienia, że ​​dany język nie jest regularny, poprzez redukcję do języka, który jest już znany jako nieregularny.

Jako bardzo prosty przykład, załóżmy, że wiemy, że język nie jest regularny. Wtedy możemy udowodnić, że język (język wszystkich słów z równie wiele s i s) nie jest regularny, jak następuje:$\{a^nb^n : n \geq 0\}$$\{w \in \{a,b\}^* : \#_a(w) = \#_b(w)\}$$a$$b$

Załóżmy, że były regularne. Wtedy również będzie normalny. Ale , o którym wiadomo, że nie jest regularny.$L = \{w \in \{a,b\}^* : \#_a(w) = \#_b(w)\}$$L \cap a^*b^*$$L \cap a^*b^* = \{a^n b^n : n \geq 0\}$

Oto bardziej skomplikowany przykład. Pokażmy, że język nie jest regularny.$L' = \{(0+1)^n2(0+1)^n : n \geq 0\}$

Niech będzie mapowaniem homomorfizmu podanym przez , , . Gdyby były regularne, to następujący język to: . Wiemy jednak, że to ostatnie nie jest regularne.$h$$h(0) = 0$$h(1) = 1$$h(2) = \epsilon$$L'$$h(L' \cap 0^*21^*) = \{ 0^n 1^n : n \geq 0 \}$

Wreszcie, oto przykład wykorzystujący odwrotny homomorfizm. Pokażmy, że język nie jest regularny.$L'' = \{0^n10^n : n \geq 0\}$

Niech będzie homomorfizmem określonym przez , , . Gdyby były regularne, to byłoby, ale to tylko język z poprzedniego przykładu.$k$$k(0) = 0$$k(1) = 0$$k(2) = 1$$L''$$k^{-1}(L'')$$L'$

Użyj teorii Myhill – Nerode.

Niech będzie językiem. Mówimy, że dwa słowa są inequivalent modulo (czyli w odniesieniu do ) jeśli istnieje słowo takiego, że dokładnie jeden jest w . W dowolnym DFA dla , (ćwiczenie). To implikuje następujące kryterium:$L$$x,y$$L$$L$$z$$xz,yz$$L$$L$$\delta(q_0,x) \neq \delta(q_0,y)$

Niech będzie językiem. Załóżmy, że istnieje nieskończony zestaw par nierównomiernych słów (to znaczy nieskończony zestaw tak że dowolne dwa nierównomierne są nierównomiernym modułem ). Wtedy nie jest regularny.$L$$S$$x,y \in S$$L$$L$

Oto prosty przykład zastosowania tego kryterium:

Język nie jest regularny.$L = \{a^nb^n : n \geq 0\}$

Dowód. Niech . Stwierdzamy, że dwie różne słowa są inequivalent modulo . Rzeczywiście, niech , gdzie . Następnie a .$S = \{ a^n : n \geq 0 \}$$S$$L$$a^i,a^j \in S$$i \ne j$$a^ib^i \in L$$a^ib^j \notin L$

Ważną cechą tej metody jest to, że gwarantuje sukces: jeśli nie jest regularne, istnieje nieskończony zestaw par nierównomiernych słów. Jest to konsekwencja twierdzenia Myhill – Nerode . W skrócie, moduł równoważności (negacja nierówności modułu zdefiniowany powyżej) jest relacją równoważności, a język jest regularny, jeżeli liczba klas równoważności modułu równoważności jest skończona. Jeśli nie jest regularne, pobranie jednego słowa z każdej klasy równoważności stanowiłoby nieskończony zestaw nierównych słów.$L$$L$$L$$L$$L$$L$

Biorąc pod uwagę język , każdy ciąg jest zbiorem ciągów takie, że . Każdy taki zestaw może być używany jako stan w maszynie stanu.$L$$x$$y$$xy \in L$

Wszystko, co musisz zrobić, to pokazać, że liczba takich zestawów nie jest skończona.

Jako przykład niech . Biorąc pod uwagę dla niektórych , jedynym ciągiem takim, że jest . Więc dla każdego mamy inny zestaw, co oznacza, że nie jest regularny.$L = {a^nb^n: n ≥ 0}$$x = a^nb$$n ≥ 1$$y$$xy \in L$$y = b^{n-1}$$n$$L$

Ogólnie rzecz biorąc, jeśli znajdziesz nieskończony zestaw ciągów taki, że każdy daje inny zestaw wówczas język nie może zostać rozpoznany przez maszynę skończoną i dlatego nie jest regularny.$x$$x$$\{y: xy \in L\}$