Лемма о разрастании

---

Лемма о накачке (лемма о разрастании, лемма-насос; англ. pumping lemma) — важное утверждение теории автоматов, позволяющее во многих случаях проверить, является ли данный язык автоматным. Поскольку все конечные языки являются автоматными, эту проверку имеет смысл делать только для бесконечных языков. Термин «накачка» в названии леммы отражает возможность многократного повторения некоторой подстроки в любой строке подходящей длины любого бесконечного автоматного языка.

Существует также лемма о разрастании для контекстно-свободных языков, ещё более общее утверждение — лемма о разрастании индексных языков.

Для бесконечного автоматного языка ${\displaystyle L}$ над алфавитом ${\displaystyle V}$ существует такое натуральное число ${\displaystyle n}$, что для любого слова ${\displaystyle \alpha \in L}$ длины не меньше ${\displaystyle n}$ найдутся слова ${\displaystyle u,v,w\in V^{*}}$ такие, что ${\displaystyle \alpha =uvw}$, ${\displaystyle |uv|\leqslant n}$, ${\displaystyle |v|\geqslant 1}$ и для всякого неотрицательного целого ${\displaystyle i}$ цепочка ${\displaystyle uv^{i}w}$ является словом языка ${\displaystyle L}$.

Пусть автоматный язык ${\displaystyle L}$ содержит бесконечное число цепочек и предположим, что ${\displaystyle L}$ распознаётся детерминированным конечным автоматом ${\displaystyle A}$ с ${\displaystyle n}$ состояниями. Для проверки заключения леммы выберем произвольную цепочку ${\displaystyle \alpha }$ этого языка, которая имеет длину ${\displaystyle n}$.

---