Lemat o pompowaniu dla języków regularnych: Różnice pomiędzy wersjami

nieformalny opis, zainspirowany enwiki
(drobne techniczne)
(nieformalny opis, zainspirowany enwiki)
[[Grafika:An automat accepting the language a(bc)*d.png|frame|300px|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 formalny|język]] nie jest [[język regularny|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:
53 594

edycje