Lemat o pompowaniu dla języków regularnych


Lemat o pompowaniu dla języków regularnych w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania Przykład automatu akceptującego język spełniający lemat o pompowaniu – a(bc)*d

Lemat o pompowaniu dla języków regularnych – twierdzenie najczęściej używane do dowodzenia, że dany język formalny nie jest językiem regularnym. Lemat brzmi[1]:

Jeśli L {\displaystyle L} jest językiem regularnym, to istnieje takie n 1 , {\displaystyle n\geqslant 1,} że w L , | w | n {\displaystyle \forall w\in L,|w|\geqslant n} istnieje podział w {\displaystyle w} na podsłowa x , y , z Σ {\displaystyle x,y,z\in \Sigma ^{*}} ( w = x y z ) , {\displaystyle (w=xyz),} t.że:
  • y ϵ {\displaystyle y\neq \epsilon }
  • | x y | n {\displaystyle |xy|\leqslant n}
  • k 0 {\displaystyle \forall k\geqslant 0} x y k z L . {\displaystyle xy^{k}z\in L.}

Nieformalnie lemat orzeka, że każde dostatecznie długie słowo w języku regularnym może być „pompowane”, tj. jego pewna środkowa część może zostać powielona dowolną liczbę razy, a powstałe słowo nadal będzie należeć do danego języka.

Spis treści

Przykład zastosowania | edytuj kod

Udowodnijmy, że język słów postaci a k b k {\displaystyle a^{k}b^{k}} dla k > 0 {\displaystyle k>0} nie jest regularny.

Załóżmy, że jest on regularny. Niech n {\displaystyle n} będzie stałą z lematu o pompowaniu. Weźmy teraz słowo a n b n {\displaystyle a^{n}b^{n}} i jego podział spełniający warunki lematu. x y {\displaystyle xy} musi leżeć w całości w części a n {\displaystyle a^{n}} słowa. Inne podziały nie są możliwe, ponieważ | x y | n , {\displaystyle |xy|\leqslant n,} więc sytuacja, w której x y = a n b p {\displaystyle xy=a^{n}b^{p}} dla pewnego p > 0 , {\displaystyle p>0,} nie może mieć miejsca. Mamy więc podział x = a q , {\displaystyle x=a^{q},} y = a p , {\displaystyle y=a^{p},} z = a n q p b n . {\displaystyle z=a^{n-q-p}b^{n}.} Zgodnie z lematem do języka należeć musiałoby też słowo x y 2 z = a q a p a p a n p q b n = a n + p b n , {\displaystyle xy^{2}z=a^{q}a^{p}a^{p}a^{n-p-q}b^{n}=a^{n+p}b^{n},} które ma jednak więcej a {\displaystyle a} niż b {\displaystyle b} i do języka nie należy.

Pokazaliśmy, że dla każdego podziału spełniającego warunki lematu istnieje k , {\displaystyle k,} wyprowadzające słowo poza język. Stąd badany język nie jest regularny.

Dowód | edytuj kod

Niech L {\displaystyle L} będzie językiem regularnym. Istnieje wtedy deterministyczny automat skończony A , {\displaystyle A,} t.że L ( A ) = L {\displaystyle L(A)=L} [2]. Załóżmy, że A {\displaystyle A} ma n {\displaystyle n} stanów. Niech w L {\displaystyle w\in L} będzie dowolnym słowem o długości co najmniej n . {\displaystyle n.} Wczytanie w {\displaystyle w} wymaga wykonania co najmniej n {\displaystyle n} przejść w automacie, co oznacza, że ścieżka odpowiadająca w {\displaystyle w} odwiedzi co najmniej n + 1 {\displaystyle n+1} stanów (wliczając stan startowy). Z zasady szufladkowej wynika, że co najmniej jeden stan A {\displaystyle A} pojawi się na ścieżce dwukrotnie.

Niech w = w i , w i + 1 , , w j {\displaystyle w'=w_{i},w_{i+1},\dots ,w_{j}} dla i < j {\displaystyle i<j} będzie podsłowem w {\displaystyle w} takim, że w trakcie wczytywania w {\displaystyle w} po wczytaniu w i {\displaystyle w_{i}} i w j {\displaystyle w_{j}} A {\displaystyle A} znalazł się w tym samym stanie P , {\displaystyle P,} dla najmniejszego możliwego j . {\displaystyle j.} Zauważmy, że j n ; {\displaystyle j\leqslant n;} gdyby tak nie było, moglibyśmy zastosować powyższy argument do początkowego fragmentu w {\displaystyle w} długości n , {\displaystyle n,} dostając w {\displaystyle w''} kończące się wcześniej niż w , {\displaystyle w',} co byłoby sprzeczne z minimalnością j . {\displaystyle j.} w {\displaystyle w'} wyznacza podział w : {\displaystyle w{:}}

  • w 1 , w 2 , , w i 1 , w i {\displaystyle w_{1},w_{2},\dots ,w_{i-1},w_{i}} oznaczmy jako x {\displaystyle x}
  • w i + 1 , w i + 2 , , w j {\displaystyle w_{i+1},w_{i+2},\dots ,w_{j}} ( w {\displaystyle w'} bez pierwszej litery) oznaczmy jako y {\displaystyle y}
  • w j + 1 , w j + 2 , , w | w | {\displaystyle w_{j+1},w_{j+2},\dots ,w_{|w|}} oznaczmy jako z , {\displaystyle z,}

przy czym:

  • | y | 1 , {\displaystyle |y|\geqslant 1,} ponieważ i < j | w | 2 | y | 1 {\displaystyle i<j\implies |w'|\geqslant 2\implies |y|\geqslant 1}
  • | x y | n , {\displaystyle |xy|\leqslant n,} ponieważ j n . {\displaystyle j\leqslant n.}

Po wczytaniu x {\displaystyle x} automat znajdzie się w stanie P . {\displaystyle P.} Wiemy, że po wczytaniu y {\displaystyle y} ten stan się nie zmieni, oraz że z {\displaystyle z} czytane od stanu P {\displaystyle P} doprowadzi automat do stanu akceptującego. Możemy wobec tego powielić y {\displaystyle y} tworząc w k = x y k z , {\displaystyle w'^{k}=xy^{k}z,} k 0. {\displaystyle k\geqslant 0.} Po wczytaniu w k {\displaystyle w'^{k}} A {\displaystyle A} znajdzie się w stanie akceptującym, a więc k 0 {\displaystyle \forall {k\geqslant 0}} w k L , {\displaystyle w'^{k}\in L,} co kończy dowód.

Zobacz też | edytuj kod

Przypisy | edytuj kod

  1. John E.J.E. Hopcroft John E.J.E., Introduction to Automata Theory, Languages, and Computation (3rd Edition), RajeevR. Motwani, Jeffrey D.J.D. Ullman, Pearson, 2006, s. 128, ISBN 978-0321455369 .
  2. John E.J.E. Hopcroft John E.J.E., Introduction to Automata Theory, Languages, and Computation (3rd Edition), RajeevR. Motwani, Jeffrey D.J.D. Ullman, Pearson, 2006, s. 92, ISBN 978-0321455369 .
Na podstawie artykułu: "Lemat o pompowaniu dla języków regularnych" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy