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

В информатике , в частности в теории формального языка , используется лемма о накачке для контекстно-свободных языков , также известная как Бар-Хиллеля лемма , — это лемма , которая дает свойство, общее для всех контекстно-свободных языков , и обобщает лемму о накачке для обычных языков .

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

Официальное заявление

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

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

$s=uvwxy$

с подстроками $u,v,w,x$ и $y$, такой, что

1. $|vx|\geq 1$,

2. $|vwx|\leq p$, и

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

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

${\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}}$

Неофициальное заявление и объяснение

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

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

Сказать $s$ это строка длиной не менее $p$ это на языке.

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

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

Использование леммы

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

Например, если $S\subset \mathbb {N}$ бесконечно, но не содержит (бесконечной) арифметической прогрессии , то $L=\{a^{n}:n\in S\}$ не является контекстно-свободным. В частности, ни простые числа , ни квадратные числа не являются контекстно-свободными.

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

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

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

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

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

$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 ≥1, выберите vwx , чтобы он состоял только из b ' s, для s = a ^я б ^дж с ^дж д ^дж выберите vwx , чтобы он состоял только из ' ' ; в обоих случаях все накачанные струны по-прежнему находятся L. в

Ссылки

• Бар-Хилель, Ю .; Мика Перлз ; Эли Шамир (1961). «О формальных свойствах простых грамматик фразовой структуры». Журнал фонетики, лингвистики и коммуникативных исследований . 14 (2): 143–172. — Перепечатано в: Ю. Бар-Гилель (1964). Язык и информация: избранные очерки по их теории и применению . Ряд Аддисона-Уэсли по логике. Аддисон-Уэсли. стр. 116–150. ISBN  0201003732 . OCLC   783543642 .
• Майкл Сипсер (1997). Введение в теорию вычислений . Издательство ПВС. ISBN  0-534-94728-Х . Раздел 1.4: Нерегулярные языки, стр. 77–83. Раздел 2.3: Неконтекстно-свободные языки, стр. 115–119.