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

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

Свою назву лема отримала з англійського дієслова to pump (укр. накачувати).В теорії формальних мов, лема про накачку для певної мови стверджує, що мова належить класу мов, якщо будь-який досить довгий рядок в мові що містить проміжок який може бути вилучений, чи повторений довільну кількість разів, і отриманий в результаті рядок теж належить мові. Доведення цих лем зазвичай комбінаторне, і може використовувати принцип Діріхле.

Два найважливіші приклади - лема про накачку для регулярних мов та . - інша, сильніша лема про накачку для контекстно-вільних мов.

Ці леми можуть бути використані для визначення чи дана мова не належить даному класу мов, і не можуть використовуватись для доведення факту приналежності мови класу, через те, що лема про накачку є тільки , а не належності класу.

Регулярні мови

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

Для кожної регулярної мови ${\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}$.

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

Джерела

Українською

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

Іншими мовами

• (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN . Section 1.4: Nonregular Languages, pp. 77–83. Section 2.3: Non-context-free Languages, pp. 115–119.
• Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Adison Wesley. ISBN . Chapter 6: Properties of Regular Languages pp. 205–210