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

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

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

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

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

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

  • Використано матеріали зі статті в англійській Вікіпедії.
  • Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  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 0-321-32221-5.  Chapter 6: Properties of Regular Languages pp. 205–210