Lemat o pompowaniu dla języków regularnych

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:

Jeżeli dany język

L

jest regularny, to istnieje takie

n > = 1

, że każde słowo w należące do L długości co najmniej

n

można podzielić na trzy części

x y v

, gdzie

y

jest niepuste i |xy| ≤ n, w taki sposób, że dla każdego

k

słowo postaci

x y k v

należy do danego języka.

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

$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 $x y 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.

[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