Lemat o pompowaniu dla języków regularnych
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]
- ↑ John E. Hopcroft , Introduction to Automata Theory, Languages, and Computation (3rd Edition), Rajeev Motwani, Jeffrey D. Ullman, Pearson, 2006, s. 128, ISBN 978-0321455369 .
- ↑ John E. Hopcroft , Introduction to Automata Theory, Languages, and Computation (3rd Edition), Rajeev Motwani, Jeffrey D. Ullman, Pearson, 2006, s. 92, ISBN 978-0321455369 .