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

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

1. $y\neq \varepsilon$
2. $|xy|\leq n$
3. $\forall k\geq 0,xy^{k}z\in L$

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

Література

• Гаврилків В. М. Формальні мови та алгоритмічні моделі. — І.-Ф.  : Голіней, 2023. — 180 с.

Див. також

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