Z Wikipedii

Lemat o pompowaniu dla języków regularnych to twierdzenie służące do dowodzenia, że dany język nie jest językiem regularnym.

Twierdzenie brzmi:

Dla danego języka regularnego istnieje takie n, że każde słowo w długości co najmniej n można podzielić na trzy części xyv, gdzie y jest niepuste i nie dłuższe niż n, w taki sposób, że dla każdego k słowo postaci xy^kv należy do danego języka.

[edytuj] Przykład

Udowodnijmy, że język słów postaci a^kb^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ⁿbⁿ. Wybór podziału jest możliwy tylko na trzy sposoby:

1. y leży w całości w części aⁿ słowa. y = a^p, x = a^q, v = a^{n − p − q}bⁿ. Wtedy do języka należeć musiałoby też słowo xy²v = a^qa^pa^pa^{n − p − q}bⁿ = a^{n + p}bⁿ, które ma jednak więcej a niż b i do języka nie należy.
2. y leży w całości w części bⁿ słowa. y = b^p, x = aⁿb^q, v = b^{n − p − q}. Wtedy do języka należeć musiałoby też słowo xy²v = aⁿb^qb^pb^pb^{n − p − q} = aⁿb^{n + p}, które ma jednak więcej b niż a i do języka nie należy
3. y leży częściowo w obu częściach słowa. y = a^pb^q, x = a^{n − p}, v = b^{n − q}. Wtedy do języka należeć musiałoby też słowo a^{n − p}a^pb^qa^pb^qb^{n − q}, w którym a i b są pomieszane, a więc które do języka też nie należy.

Ponieważ nie jesteśmy w stanie zbudować żadnego podziału, język ten nie jest regularny.

[edytuj] 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