Lemat o pompowaniu dla języków regularnych

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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^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. 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.
  2. y leży w całości w części b^n słowa. y=b^p, x=a^nb^q, v=b^{n-p-q}. Wtedy do języka należeć musiałoby też słowo xy^2v = a^nb^qb^pb^pb^{n-p-q} = a^nb^{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.

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]