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

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

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

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

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

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

Регулярні мови[ред.ред. код]

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

Для кожної регулярної мови L існує натуральне число n, таким чином, що виконується: Кожне слово z в L з найкоротшою довжиною n можна розкласти як z = uvw з наступними властивостями:

  1. Обидва слова u та v разом мають довжину максимум n. Тобто |uv| \le n.
  2. Слово v повинно бути не пустим, іншими словами, складатися з одного чи більше символів. Тобто |v| \ge 1.
  3. Для кожного натурального числа (включаючи нуль) i слово uv^iw належить мові L, тобто слова uw, uvw, uvvw, uvvvw і т.д. всі належать мові L.

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

Джерела[ред.ред. код]