Lemat o pompowaniu dla języków regularnych

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
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.

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^kv należy do danego języka.

Przykład[edytuj | edytuj kod]

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^nb^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ść xy 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^2v = a^qa^pa^pa^{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[edytuj | edytuj kod]

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