Лемма о разрастании для КС-грамматик

Лемма (о разрастании КС-грамматик):

Пусть [math]L[/math] — контекстно-свободный язык над алфавитом [math]\Sigma[/math], тогда существует такое [math]n[/math], что для любого слова [math] \omega \in L[/math] длины не меньше [math]n[/math] найдутся слова [math] u,v,x,y,z \in \Sigma^*[/math], для которых верно: [math]uvxyz=\omega, vy\neq \varepsilon, |vxy|\leqslant n[/math] и [math]\forall k \geqslant 0~uv^{k}xy^{k}z\in L[/math].

Доказательство:

[math]\triangleright[/math]

Грамматика любого контекстно-свободного языка может быть записана в нормальной форме Хомского (НФХ). Пусть [math]m[/math] — количество нетерминалов в грамматике языка [math]L[/math], записанной в НФХ. Выберем [math]n=2^{m+1}[/math]. Построим дерево разбора произвольного слова [math]\omega[/math] длиной больше, чем [math]n[/math]. Высотой дерева разбора назовем максимальное число нетерминальных символов на пути от корня дерева к листу. Так как грамматика языка [math]L[/math] записана в НФХ, то у любого нетерминала в дереве могут быть, либо два потомка нетерминала, либо один потомок терминал. Поэтому высота дерева разбора слова [math]\omega[/math] не меньше [math]m+1[/math]. Количество нетерминалов в нем не меньше, чем [math]m+1[/math], следовательно, найдется такой нетерминал [math]B[/math], который встречается на этом пути дважды. Значит, в дереве разбора найдется нетерминал [math]B[/math], в поддереве которого содержится нетерминал [math]B[/math]. Выберем нетерминал [math]A[/math], у которого в поддереве содержится такой же нетерминал и длина пути до корня максимальна среди всех нетерминалов, содержащих в поддереве такой же нетерминал. Найдем слова [math] u,v,x,y,z [/math]. Рассмотрим нетерминал [math]A[/math], содержащийся в поддереве выбранного нетерминала. Тогда [math]x[/math] - строка терминалов которая выведена из рассмотренного нетерминала в данном дереве разбора. [math]A \Rightarrow^{*} x[/math]. Рассмотрим выбранный нетерминал [math]A[/math]. Пусть [math]t[/math] - строка терминальных символов, которая выведена из рассмотренного нетерминала в данном дереве разбора. Тогда [math]A \Rightarrow^{*}\alpha A \beta \Rightarrow^{*} t[/math], где [math]\alpha,\beta[/math] - строки, состоящие из терминалов, которые могут содержать как терминалы, так и нетерминалы. При этом, как минимум одна из строк [math]\alpha,\beta[/math] не пуста, так как грамматика языка записана в НФХ. Пусть [math]v,y[/math] - строки, состоящие из терминалов, которые выведены из [math]\alpha,\beta[/math] соответственно, в данном дереве разбора. Тогда [math]t = vxy[/math]. Так как хотя бы одна из строк [math]\alpha,\beta[/math] не пуста, то [math]vy\neq \varepsilon[/math]. Получаем [math]A \Rightarrow^{*} vAy \Rightarrow^{*} vxy[/math]. Рассмотрим стартовый нетерминал [math]S[/math]. Из [math]S[/math] выведена строка [math]\omega[/math]. При этом [math]S \Rightarrow^{*} \alpha A \beta \Rightarrow^{*} \omega [/math], где [math]A[/math] - выбранный ранее нетерминал. Из [math]A[/math] в данном дереве разбора выведена строка [math]vxy[/math]. Пусть [math]u,z[/math] - строки, состоящие из терминалов, которые выведены из [math]\alpha,\beta[/math] соответственно, в данном дереве разбора. Тогда [math]S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} \omega[/math]. Таким образом, в рамках нашей грамматики мы можем построить цепочку вывода: [math]S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} uvvAyyz \Rightarrow^{*} uv^{k}Ay^{k}z \Rightarrow^{*} uv^{k}xy^{k}z[/math].

[math]\triangleleft[/math]

Замечание. Условие леммы не является достаточным для контекстно-свободности языка. Но в силу необходимости, данная лемма часто используется для доказательства неконтекстно-свободности языков.

Пример доказательства неконтекстно-свободности языка с использованием леммы

Рассмотрим язык [math]0^{n}1^{n}2^{n}[/math]. Покажем, что он не является контекстно-свободным. Для фиксированного [math]n[/math] рассмотрим слово [math]\omega=0^n 1^n 2^n[/math]. Пусть [math]\omega[/math] разбили на [math]u, v, x, y, z[/math] произвольным образом. Так как [math]|vxy|\leqslant n[/math], то в слове не содержится либо ни одного символа [math]0[/math], либо ни одного символа [math]2[/math]. Для любого такого разбиения выберем [math]k=2[/math] и получаем, количество символов 1 изменилось, а количество либо [math]0[/math], либо [math]2[/math] осталось тем же. Очевидно, что такое слово не принадлежит рассмотренному языку. Значит, язык [math]0^{n}1^{n}2^{n}[/math] не является контекстно-свободным.

Источники

• Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)