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