ТМВ-2020-Лекция-17.03.2020

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

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

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

Формулировка

Для любого КС - свободного языка \(\exists n :\) любое слово \(\omega\) длины \(|\omega| > n\), представимо в виде:

\(\omega = uvxyz\),

где \(u,v,x,y,z\) - слова языка и:

1) \(vy\neq\lambda\)

2) \(|vxy| < n\)

3) \(uv^kxy^kz\) - принадлежит этому языку

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

Пусть грамматика записана в Нормальной Форме Хомского.

\(|N| = M\)

Возьмем \(n = 2^{M+1}\). Построим дерево разбора слова \(\sigma\) высотой h (максимальное число нетерминальных символов на пути от корня дерева к листу), где \(|\sigma| > n\), \(h \geqslant M+1\).

Произвольное дерево разбора2.png


Хотя бы один путь содержит длину M+1, возьмем самый длинный путь (который содержит M+1 нетерминал), соответственно, хотя бы один нетерминал по длиннейшему пути из корня в лист повторяется дважды.

2 одинаковых нетерминала в дереве разбора.png

Узнаём:

1) \(B^* \rightarrow x\) (x - строка терминалов, которая выведена из рассмотренного нетерминала)

2) \(B \rightarrow vBy\) , причем (\(|vy| > 0\) - хотя бы одна строка непуста)

3) \(S^* \rightarrow uBz \)

4) \(S^* \rightarrow uvByz\)

5) \(S \rightarrow uv^kBy^kz\)

Пусть \(|vxy|>n=2^{M+1}\), следовательно \(h_B \geqslant M+2\), соответственно в поддереве(см. рисунок выше черный треугольник) есть более одного нетерминала, повторяющегося дважды, следовательно верно утверждение 6:

6) \(|vxy| \leqslant n\)

Таким образом, мы можем построить цепочку вывода:

\(S \rightarrow uBz \rightarrow uvByz \rightarrow uv^kBy^kz \rightarrow uv^kxy^kz\) ∎