Лема про накачку

Для кожної регулярної мови ${\displaystyle L}$ існує натуральне число ${\displaystyle n}$, таким чином, що виконується: Кожне слово ${\displaystyle z}$ в ${\displaystyle L}$ з найкоротшою довжиною ${\displaystyle n}$ можна розкласти як ${\displaystyle z=uvw}$ з наступними властивостями:

1. Обидва слова ${\displaystyle u}$ та ${\displaystyle v}$ разом мають довжину максимум ${\displaystyle n}$. Тобто ${\displaystyle |uv|\leq n}$.
2. Слово ${\displaystyle v}$ повинно бути не пустим, іншими словами, складатися з одного чи більше символів. Тобто ${\displaystyle |v|\geq 1}$.
3. Для кожного натурального числа (включаючи нуль) ${\displaystyle i}$ слово ${\displaystyle uv^{i}w}$ належить мові ${\displaystyle L}$, тобто слова ${\displaystyle uw}$, ${\displaystyle uvw}$, ${\displaystyle uvvw}$, ${\displaystyle uvvvw}$ і т.д. всі належать мові ${\displaystyle L}$.

Крім регулярних мов існують також нерегулярні мові, для яких ця лема виконується. Необхідну та достасню умову для регулярних мов надають теорема Майхілла-Нероуда чи лема про накачку Яффе.