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

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

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

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

Література

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

Див. також

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