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^[1]:

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

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

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

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

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

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

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

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

przy czym:

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

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

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