Lemat o pompowaniu dla języków regularnych

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:

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

• $y\ne ϵ$
• $|xy|⩽n$
• $\mathrm{\forall }k⩾0$ $x{y}^{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|⩽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 $x{y}^{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^{\prime }=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⩽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^{\prime },$ co byłoby sprzeczne z minimalnością $j.$ $w^{\prime }$ 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^{\prime }$ bez pierwszej litery) oznaczmy jako $y$
• $w_{j+1},w_{j+2},\dots ,w_{|w|}$ oznaczmy jako $z,$

przy czym:

• $|y|⩾1,$ ponieważ $i<j⟹|w^{\prime }|⩾2⟹|y|⩾1$
• $|xy|⩽n,$ ponieważ $j⩽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{\text{'}}^k=x{y}^{k}z,$ $k⩾0.$ Po wczytaniu $w{\text{'}}^k$ $A$ znajdzie się w stanie akceptującym, a więc $\mathrm{\forall }k⩾0$ $w{\text{'}}^k\in L,$ co kończy dowód.

Zobacz też

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