Dowód Niech będzie językiem regularnym. Istnieje wtedy deterministyczny automat skończony t.że . 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ż lemat o pompowaniu dla języków bezkontekstowych język regularny
Przypisy
Kategoria:Języki formalne O