Lemat o pompowaniu dla języków regularnych

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:

Przykład automatu akceptującego język spełniający lemat o pompowaniu – a(bc)*d

Jeśli $L$ jest językiem regularnym, to istnieje takie $n\geqslant 1,$ że $\forall w\in L,|w|\geqslant n$ istnieje podział $w$ na podsłowa $x,y,z\in \Sigma ^{*}$ $(w=xyz),$ t.że:

• $y\neq \epsilon$
• $|xy|\leqslant n$
• $\forall k\geqslant 0$ $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.

Przykład zastosowania

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

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

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

Dowód

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

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

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

przy czym:

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

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

Zobacz też

• lemat o pompowaniu dla języków bezkontekstowych
• język regularny