Лемма о накачке

В теории формальных языков лемма о накачке может относиться к:

Лемма о накачке для регулярных языков , тот факт, что все достаточно длинные строки в таком языке имеют подстроку, которая может повторяться произвольное количество раз, обычно используется для доказательства того, что определенные языки не являются регулярными.
Лемма о накачке для контекстно-свободных языков , тот факт, что все достаточно длинные строки в таком языке имеют пару подстрок, которые могут повторяться произвольное количество раз, обычно используется для доказательства того, что определенные языки не являются контекстно-свободными.
Лемма о прокачке для индексируемых языков
Лемма о накачке для обычных древовидных языков

См. также

Лемма Огдена , более сильная версия леммы о накачке для контекстно-свободных языков.

Эта статья включает список связанных элементов, имеющих одно и то же имя (или похожие имена).
Если внутренняя ссылка привела вас сюда по ошибке, вы можете изменить ссылку, чтобы она указывала непосредственно на нужную статью.