Оценка длины цепочки

Пусть L(G) - некоторый e-свободный КС-язык, причем G - грамматика в НФХ.

Теорема: Если некоторая цепочка х языка L(G) имеет дерево вывода глубины m, то длина цепочки |x|£ 2^m-1.

Следствие: Если длина некоторой цепочки |x|>2^m, то дерево вывода имеет глубину более чем m.

Основная теорема КС-языков:

Пусть L - КС-язык, порожденный грамматикой G в НФХ. Тогда существуют целые числа l₁ и l₂ такие, что для любой zÌL, длина которой |z|>l₁ справедливо следующее утверждение:

z= uvwxy.

1. длина цепочки |vwx|£l₂;

2. цепочка vx¹e;

3. для любых i³0 существует цепочка uvⁱwxⁱy.

Доказательство: Положим n= |N| - мощность множества нетерминалов. Возьмем l₁= 2^n-1 и l₂= 2ⁿ. По условию теоремы |z|>2^n-1, тогда глубина дерева больше n. На этом пути обязательно встретятся два одинаковых нетерминала. Возьмем два таких нетерминала, которые дальше всего отстоят от корня. Начиная с N₁ путь имеет длину не более n+1. Таким образом, длина цепочки, выводимой из вершины N₁ не более, чем 2ⁿ. Значит любая цепочка, выводимая из N₁ не больше 2ⁿ.

|vwx|<2ⁿ= l₂ и vx¹e, так как из N₁ выходят две дуги.

A®*vAx и A®*w, следовательно A®*vwx. Тогда A®*vAx®*v²Ax²®* vⁱAxⁱ. Следовательно, S®*uAy®* uvⁱwxⁱy.

Вопросы и упражнения

Пусть задана грамматика G=(T, N, S, P):

S®AB

A®ba

B®с

1.Постройте вывод цепочки в данной грамматики.

2.Постройте для полученной цепочки дерево вывода.

3. Сравните длину цепочки и глубину дерева вывода. Верна ли данная теорема?