Лемма о перекачке для контекстно-свободных языков - Pumping lemma for context-free languages
В Информатика, в частности в формальная теория языка, то лемма о накачке для контекстно-свободных языков, также известный как Бар-Гилель[требуется разъяснение ] лемма, это лемма что дает собственность, разделяемую всеми контекстно-свободные языки и обобщает лемма о накачке для регулярных языков.
Лемму о накачке можно использовать для построения доказательство от противного что конкретный язык нет контекстно-свободный. Наоборот, леммы о накачке недостаточно, чтобы гарантировать, что язык является контекстно-свободный; есть другие необходимые условия, такие как Лемма Огдена, или Лемма об обмене.
Официальное заявление
Если язык не зависит от контекста, то существует некоторое целое число (называется «длина накачки»[1]) такой, что каждая строка в что есть длина из или более символов (т.е. с ) можно записать как
с подстроки и , так что
- 1. ,
- 2. , и
- 3. для всех .
Ниже приводится формальное выражение леммы о накачке.
Неофициальное заявление и объяснение
Лемма о подкачке для контекстно-свободных языков (называемая просто «леммой о подкачке» в оставшейся части этой статьи) описывает свойство, которое гарантированно имеет все контекстно-свободные языки.
Свойство - это свойство всех строк на языке, длина которых не менее , куда является константой, называемой длина откачки- это зависит от контекстно-свободных языков.
Сказать строка длиной не менее это на языке.
Лемма о накачке утверждает, что можно разбить на пять подстрок, , куда не пусто, а длина самое большее , так что повторение и такое же количество раз () в производит строку, которая все еще находится на языке. Часто бывает полезно повторить ноль раз, что удаляет и из строки. Этот процесс «подкачки» дополнительных копий и это то, что дало название лемме о накачке.
Конечные языки (которые являются регулярными и, следовательно, контекстно-свободными) подчиняются лемме о накачке тривиально, имея равна максимальной длине строки в плюс один. Поскольку струн такой длины нет, лемма о накачке не нарушается.
Использование леммы
Лемма о накачке часто используется для доказательства того, что данный язык L неконтекстно-бесконтекстно, показывая, что произвольно длинные строки s находятся в L которые нельзя «накачать», не производя струн снаружи L.
Например, язык можно показать, что он неконтекстно-независимый, используя лемму о накачке в доказательство от противного. Сначала предположим, что L контекстно-свободный. По лемме о накачке существует целое число п что является накачивающей длиной языка L. Рассмотрим строку в L. Лемма о накачке говорит нам, что s можно записать в виде , куда u, v, w, x, и y подстроки, такие что , , и для каждого целого числа . По выбору s и тот факт, что , легко видеть, что подстрока vwx может содержать не более двух различных символов. То есть у нас есть одна из пяти возможностей для vwx:
- для некоторых .
- для некоторых j и k с
- для некоторых .
- для некоторых j и k с .
- для некоторых .
В каждом случае легко проверить, что не содержит равных номеров каждой буквы для любого . Таким образом, не имеет формы . Это противоречит определению L. Поэтому наше первоначальное предположение, что L не зависит от контекста должно быть ложным.
Хотя лемма о перекачке часто является полезным инструментом для доказательства того, что данный язык не является контекстно-независимым, она не дает полной характеристики контекстно-свободных языков. Если язык не удовлетворяет условию, заданному леммой о накачке, мы установили, что он не является контекстно-независимым.
С другой стороны, есть языки, которые не являются контекстно-независимыми, но все же удовлетворяют условию, заданному леммой о накачке, например
за s=бjckdл например, с j≥1 выбрать vwx состоять только из бДля s=аябjcjdj выберите vwx состоять только из аS; в обоих случаях все накачанные струны все еще в L.[2]
Предшественник леммы о накачке был использован в 1960 году Шейнбергом для доказательства того, что не является контекстно-зависимым.[3]
Рекомендации
- ^ Берстель, Жан; Лаув, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009). Комбинаторика слов. Кристоффель слова и повторы словами (PDF). Серия монографий CRM. 27. Провиденс, Род-Айленд: Американское математическое общество. п. 90. ISBN 978-0-8218-4480-9. Zbl 1161.68043. (См. Также [www-igm.univ-mlv.fr/~berstel/ веб-сайт Аарона Берштеля)
- ^ Джон Э. Хопкрофт, Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления. Эддисон-Уэсли. ISBN 0-201-02988-X. Здесь: раздел 6.1, с.129
- ^ Стивен Шейнберг (1960). «Замечание о булевых свойствах контекстно-свободных языков» (PDF). Информация и контроль. 3: 372–375. Дои:10.1016 / s0019-9958 (60) 90965-7. Здесь: лемма 3 и ее использование на стр.374-375.
- Бар-Гилель, Ю.; Миха Перлес; Эли Шамир (1961). «О формальных свойствах грамматик простой фразеологической структуры». Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung. 14 (2): 143–172. - Печатается на: Ю. Бар-Гиллель (1964). Язык и информация: избранные эссе по их теории и применению. Логика серии Аддисона-Уэсли. Эддисон-Уэсли. С. 116–150. ISBN 0201003732. OCLC 783543642.
- Майкл Сипсер (1997). Введение в теорию вычислений. PWS Publishing. ISBN 0-534-94728-X. Раздел 1.4: Нерегулярные языки, стр. 77–83. Раздел 2.3: Неконтекстно-свободные языки, стр. 115–119.