Лемма о накачке - Pumping lemma

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

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

Смотрите также

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

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