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 jest regularny, to istnieje takie , że każde słowo w należące do L długości co najmniej można podzielić na trzy części , gdzie jest niepuste i |xy| < n, w taki sposób, że dla każdego słowo postaci należy do danego języka.

Przykład[edytuj]

Udowodnijmy, że język słów postaci nie jest regularny.

Załóżmy, że jest on regularny. Niech będzie stałą z lematu o pompowaniu. Weźmy teraz słowo i jego podział spełniający warunki lematu. Wtedy:

  1. leży w całości w części słowa. , , . Wtedy do języka należeć musiałoby też słowo , które ma jednak więcej niż i do języka nie należy.

Inne podziały nie są możliwe ponieważ |xy|<n ,wynika z tego, że język nie jest regularny.

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]

Jeśli dany język jest regularny, możemy dla niego zbudować deterministyczny automat skończony. Wybierzmy dowolny z takich automatów – ma on stanów. Weźmy teraz dowolne słowo o długości co najmniej . Ponieważ miejsc między znakami (wliczając w to miejsce przed pierwszym oraz po ostatnim znaku) jest więcej niż , 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ż , 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 . Podzielmy słowo na trzy części:

  • część przed tym fragmentem oznaczmy jako
  • wybrany fragment oznaczmy jako
  • część po tym fragmentem oznaczmy jako

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

Zobacz też[edytuj]