Lemat o pompowaniu dla języków regularnych

Przykład automatu spełniającego Lemat o pompowaniu - a(bc)*d

Lemat o pompowaniu dla języków regularnych – twierdzenie służące do dowodzenia, że dany język nie jest językiem regularnym. Nieformalnie - dostatecznie długie słowo w języku regularnym może być pompowane, tj. jego środkowa część może zostać powtórzona dowolną ilość razy a powstałe słowo nadal będzie należeć do tego języka.

Twierdzenie brzmi:

Jeżeli dany język $L$ jest regularny, to istnieje takie $n\geq 1$, że każde słowo w należące do L długości co najmniej $n$ można podzielić na trzy części $xyv$, gdzie $y$ jest niepuste i |xy| ≤ n, w taki sposób, że dla każdego $k\geq 0$ słowo postaci $xy^{k}v$ należy do danego języka.

Przykład

Udowodnijmy, że język słów postaci $a^{k}b^{k}$ 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. Wtedy:

1. $y$ leży w całości w części $a^{n}$ słowa, gdyż długość $x$$y$ jest mniejsza od $n$. $y=a^{p}$, $x=a^{q}$, $v=a^{n-p-q}b^{n}$. Wtedy do języka należeć musiałoby też słowo $xy^{2}v=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

Jeśli dany język jest regularny, możemy dla niego zbudować deterministyczny automat skończony. Wybierzmy dowolny z takich automatów – ma on $n$ stanów. Weźmy teraz dowolne słowo o długości co najmniej $n$. Ponieważ miejsc między znakami (wliczając w to miejsce przed pierwszym oraz po ostatnim znaku) jest więcej niż $n$, przynajmniej dwa z nich znajdą się w tym samym stanie.

Weźmy dowolny fragment słowa na początku i końcu którego jest ten sam stan. Jeśli fragment jest dłuższy niż $n$, na podstawie tego samego argumentu można udowodnić, że istnieje wewnątrz niego krótszy fragment o tej samej właściwości. Weźmy więc taki fragment, który ma długość nie większą od $n$. Podzielmy słowo na trzy części:

• część przed tym fragmentem oznaczmy jako $x$
• wybrany fragment oznaczmy jako $y$
• część po tym fragmentem oznaczmy jako $v$

Automat zaczyna w stanie startowym $S$, po przejściu $x$ znajduje się w pewnym stanie $A$. Teraz może przejść $y$ dowolną ilość razy – 0, 1, 2, czy też kilka milionów – i nadal będzie się znajdował w stanie $A$. Zgodnie z założeniem, że słowo należało do języka, automat zaczynając ze stanu $A$ i przeczytawszy $v$ kończy w stanie akceptującym.

Zobacz też

• Lemat o pompowaniu dla języków bezkontekstowych