Lemat o pompowaniu Załóżmy, że dany język jest regularny. Wtedy istnieje taka stała że dla każdego słowa należącego do tego języka i dłuższego niż możemy to słowo podzielić na trzy części z czego i i dla każdego całkowitego nieujemnego, należy do języka.
Przykład Weźmy język czyli wszystkich słów składających się z znaków po których występuje znaków dla dowolnego naturalnego.
Weźmy słowo gdzie jest większe od stałej z lematu o pompowaniu. Wobec warunku z lematu, leży w całości w części Wtedy ma więcej znaków niż gdyż Zatem słowo nie należy do wbrew tezie lematu o pompowaniu.
Ponieważ nie spełnia lematu o pompowaniu, to nie jest regularny.
Kategoria:Języki formalne