Лема про накачку для регулярних мов

Лема про накачку для регулярних мов формулюється так: Нехай L — регулярна мова. Існує константа n (залежна від L), для якої кожен ланцюжок $w$ з мови L, який задовільняє нерівність $|w|\ge n$, можна розбити на ланцюжки $w=xyz$ так, що виконуються наступні умови:

1. $y\ne \epsilon$
2. $|xy|\le n$
3. $\mathrm{\forall }k\ge 0,x{y}^{k}z\in L$

Це означає, що завжди можна знайти такий ланцюжок $y$ недалеко від початку ланцюжка $w$, який можна «накачати». Таким чином якщо ланцюжок y повторити будь-яку кількість разів або видалити (при $k=0$), то результуючий ланцюжок все одно буде належати мові L.

Література

• Шаблон:Книга

Див. також

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