Лемма о перекачке для контекстно-свободных языков

В компьютерной науке , в частности , в теории формальных языков , то насосная лемма для контекстно-свободных языков , также известный как Бар-Гиллель леммы , ^[1] является лемма , которая дает свойство , разделяемое всеми контекстно-свободных языков и обобщает накачку лемма для обычных языков .

Лемму о накачке можно использовать для построения доказательства от противного, что конкретный язык не является контекстно-независимым. С другой стороны , накачка лемма не достаточно , чтобы гарантировать , что язык является контекстно-свободной; есть другие необходимые условия, такие как лемма Огдена или лемма об обмене .

Официальное заявление [ править ]

Доказательство идея: Если достаточно долго, его вывод дерево WRT в нормальной форме Хомской грамматики должно содержать некоторый нетерминал дважды на некотором дереве пути (верхний рисунок). Повторяя раз, выводная часть ⇒ ... ⇒ получает вывод для (нижний левый и правый рисунок для и , соответственно).${\ displaystyle s}$ ${\ displaystyle N}$${\ displaystyle n}$${\ displaystyle N}$${\ displaystyle vNx}$${\ displaystyle uv ^ {n} wx ^ {n} y}$${\ displaystyle n = 0}$${\ displaystyle 2}$

Если язык является контекстно-свободным, то существует некоторое целое число (называемое «накачка длиной» ^[2] ), что каждая строка в том , что имеет длину от или более символов (т.е. с ) можно записать в виде${\ displaystyle L}$${\ displaystyle p \ geq 1}$${\ displaystyle s}$${\ displaystyle L}$${\ displaystyle p}$${\ displaystyle | s | \ geq p}$

${\ displaystyle s = uvwxy}$

с подстроками и такими, что${\ displaystyle u, v, w, x}$${\ displaystyle y}$

1. ,${\ displaystyle | vx | \ geq 1}$

2. , и${\ displaystyle | vwx | \ leq p}$

3. для всех .${\ displaystyle uv ^ {n} wx ^ {n} y \ in L}$${\ Displaystyle п \ geq 0}$

Ниже приводится формальное выражение леммы о накачке.

${\displaystyle {\begin{array}{l}(\forall L\subseteq \Sigma ^{*})\\\quad ({\mbox{context free}}(L)\Rightarrow \\\quad ((\exists p\geq 1)((\forall s\in L)((|s|\geq p)\Rightarrow \\\quad ((\exists u,v,w,x,y\in \Sigma ^{*})(s=uvwxy\land |vx|\geq 1\land |vwx|\leq p\land (\forall n\geq 0)(uv^{n}wx^{n}y\in L)))))))\end{array}}}$

Неофициальное заявление и объяснение [ править ]

Лемма о подкачке для контекстно-свободных языков (называемая просто «леммой о подкачке» в остальной части этой статьи) описывает свойство, которое гарантированно имеет все контекстно-свободные языки.

Свойство - это свойство всех строк в языке, длина которых не меньше , где - константа, называемая длиной накачки , которая варьируется между контекстно-свободными языками.${\displaystyle p}$${\displaystyle p}$

Say - это строка, длина которой не меньше длины на языке.${\displaystyle s}$${\displaystyle p}$

В лемме о перекачке говорится, что можно разбить на пять подстрок,, где не пусто, а длина не больше , так что повторение и такое же количество раз ( ) в производит строку, которая все еще находится на языке. Часто бывает полезно повторить ноль раз, что удаляет и из строки. Этот процесс «накачки» дополнительных копий и дал название лемме о накачке.${\displaystyle s}$${\displaystyle s=uvwxy}$${\displaystyle vx}$${\displaystyle vwx}$${\displaystyle p}$${\displaystyle v}$${\displaystyle x}$${\displaystyle n}$${\displaystyle s}$${\displaystyle v}$${\displaystyle x}$${\displaystyle v}$${\displaystyle x}$

Конечные языки (которые являются регулярными и, следовательно, контекстно-свободными) подчиняются лемме о перекачке тривиально, поскольку длина строки равна максимальной длине строки плюс один. Поскольку струн такой длины нет, лемма о накачке не нарушается.${\displaystyle p}$${\displaystyle L}$

Использование леммы [ править ]

Насосная лемма часто используется для доказательства того, что данный язык L не является контекстно-свободной, показывая , что сколь угодно длинные строки s в L , которые не могут быть «накачкой» , не производя струне вне L .

Например, можно показать , что язык неконтекстно-свободный, используя лемму о накачке в доказательстве от противного . Во-первых, предположим, что L не зависит от контекста. По перекачиваемой лемме, существует целое число р , которое является длиной накачки языка L . Рассмотрим строку в L . Насосная лемму говорит о том , что ей может быть записана в виде , где U, V, W, X и Y являются подстроки, такие , что , и для каждого целого числа . По выбору s и тому факту , что подстрока vwx${\displaystyle L=\{a^{n}b^{n}c^{n}|n>0\}}$${\displaystyle s=a^{p}b^{p}c^{p}}$${\displaystyle s=uvwxy}$${\displaystyle |vx|\geq 1}$${\displaystyle |vwx|\leq p}$${\displaystyle uv^{i}wx^{i}y\in L}$${\displaystyle i\geq 0}$${\displaystyle |vwx|\leq p}$может содержать не более двух различных символов. То есть у нас есть одна из пяти возможностей для vwx :

1. ${\displaystyle vwx=a^{j}}$для некоторых .${\displaystyle j\leq p}$
2. ${\displaystyle vwx=a^{j}b^{k}}$для некоторых j и k с${\displaystyle j+k\leq p}$
3. ${\displaystyle vwx=b^{j}}$для некоторых .${\displaystyle j\leq p}$
4. ${\displaystyle vwx=b^{j}c^{k}}$для некоторых j и k с .${\displaystyle j+k\leq p}$
5. ${\displaystyle vwx=c^{j}}$для некоторых .${\displaystyle j\leq p}$

Для каждого случая легко проверить, что не содержит одинаковых номеров каждой буквы ни для одной . Таким образом, не имеет формы . Это противоречит определению L . Следовательно, наше первоначальное предположение о том, что L контекстно-свободно, должно быть ложным.${\displaystyle uv^{i}wx^{i}y}$${\displaystyle i\neq 1}$${\displaystyle uv^{2}wx^{2}y}$${\displaystyle a^{i}b^{i}c^{i}}$

Хотя лемма о перекачке часто является полезным инструментом для доказательства того, что данный язык не является контекстно-независимым, она не дает полной характеристики контекстно-свободных языков. Если язык не удовлетворяет условию леммы о накачке, мы установили, что он не является контекстно-независимым.

С другой стороны, есть языки, которые не являются контекстно-независимыми, но все же удовлетворяют условию, заданному леммой о накачке, например

${\displaystyle L=\{b^{j}c^{k}d^{l}|j,k,l\in \mathbb {N} \}\cup \{a^{i}b^{j}c^{j}d^{j}|i,j\in \mathbb {N} ,i\geq 1\}}$

для s = b ^j c ^k d ^l, например, j ≥1, выберите vwx, чтобы он состоял только из b ’s, для s = a ⁱ b ^j c ^j d ^j выберите vwx, чтобы он состоял только из a ’ s; в обоих случаях все накачкой строки все еще находятся в L . ^[3]

Предшественник леммы о накачке был использован в 1960 году Шейнбергом, чтобы доказать, что это не является контекстно- зависимым . ^[4]${\displaystyle L=\{a^{n}b^{n}a^{n}|n>0\}}$

Ссылки [ править ]

• Бар-Гилель, Ю .; Миха Перлес ; Эли Шамир (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.