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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Див. також[ред.ред. код]


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.