Lemat o pompowaniu dla języków regularnych

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Przykład automatu akceptującego język spełniający lemat o pompowaniu – a(bc)*d

Lemat o pompowaniu dla języków regularnych – twierdzenie najczęściej używane do dowodzenia, że dany język formalny nie jest językiem regularnym. Lemat brzmi[1]:

Jeśli jest językiem regularnym, to istnieje takie że istnieje podział na podsłowa t.że:

Nieformalnie lemat orzeka, że każde dostatecznie długie słowo w języku regularnym może być „pompowane”, tj. jego pewna środkowa część może zostać powielona dowolną liczbę razy, a powstałe słowo nadal będzie należeć do danego języka.

Przykład zastosowania[edytuj | edytuj kod]

Udowodnijmy, że język słów postaci dla 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. musi leżeć w całości w części słowa. Inne podziały nie są możliwe, ponieważ więc sytuacja, w której dla pewnego nie może mieć miejsca. Mamy więc podział Zgodnie z lematem do języka należeć musiałoby też słowo które ma jednak więcej niż i do języka nie należy.

Pokazaliśmy, że dla każdego podziału spełniającego warunki lematu istnieje wyprowadzające słowo poza język. Stąd badany język nie jest regularny.

Dowód[edytuj | edytuj kod]

Niech będzie językiem regularnym. Istnieje wtedy deterministyczny automat skończony t.że [2]. Załóżmy, że ma stanów. Niech będzie dowolnym słowem o długości co najmniej Wczytanie wymaga wykonania co najmniej przejść w automacie, co oznacza, że ścieżka odpowiadająca odwiedzi co najmniej stanów (wliczając stan startowy). Z zasady szufladkowej wynika, że co najmniej jeden stan pojawi się na ścieżce dwukrotnie.

Niech dla będzie podsłowem takim, że w trakcie wczytywania po wczytaniu i znalazł się w tym samym stanie dla najmniejszego możliwego Zauważmy, że gdyby tak nie było, moglibyśmy zastosować powyższy argument do początkowego fragmentu długości dostając kończące się wcześniej niż co byłoby sprzeczne z minimalnością wyznacza podział

  • oznaczmy jako
  • ( bez pierwszej litery) oznaczmy jako
  • oznaczmy jako

przy czym:

  • ponieważ
  • ponieważ

Po wczytaniu automat znajdzie się w stanie Wiemy, że po wczytaniu ten stan się nie zmieni, oraz że czytane od stanu doprowadzi automat do stanu akceptującego. Możemy wobec tego powielić tworząc Po wczytaniu znajdzie się w stanie akceptującym, a więc co kończy dowód.

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

  1. John E. Hopcroft, Introduction to Automata Theory, Languages, and Computation (3rd Edition), Rajeev Motwani, Jeffrey D. Ullman, Pearson, 2006, s. 128, ISBN 978-0321455369.
  2. John E. Hopcroft, Introduction to Automata Theory, Languages, and Computation (3rd Edition), Rajeev Motwani, Jeffrey D. Ullman, Pearson, 2006, s. 92, ISBN 978-0321455369.