Изменения
Нет описания правки
Лемма:
<tex>\forall \Gamma : \exists k \ge 1: z \in L(\Gamma), |z| \ge k</tex> и в z выбраны хотябы k позиций, то z представимо в виде <tex>z = uvwxy</tex>, где <tex>uvw</tex> или <tex>wxy</tex> содержат хотя бы по одной выбранной позиции и <tex>vwx</tex> содержит не более k выбраных позиций и <tex>\exists A</tex> - нетерминал, такой, что <tex>\forall i: S \Rightarrow^* uAy \Rightarrow^* uvAxy \Rightarrow^* uv^i Ax^i y \Rightarrow^* uv^i wx^i y</tex>.
Доказательство:
Пусть в грамматике m нетерминалов, длина всех правых частей не превосходит l, значит высота дерева разбора хотя бы 2m+1.
Выбираем <tex>k=l^{2m+3}</tex>
Вершина ветвится, если хотя бы 2 ребенка.
Если есть сын с помечеными детьми в поддереве - идем в него, ветвится - идем где больше.
Вершина ветвится влево, если слева от него есть помеченные листья. Так же определяеся ветвление вправо.
Одного из этих типов хотя бы m+2.
Пусть m+2 ветвится влево. Рассмотрим нижние m+1 - среди них встретится повторяющийся нетерминал A. Для него уже выполнено условие леммы. В частности uvw - помечены. Из всех прочих выбираем один, в средней части не более k помеченных.
{{Теорема
|statement=
Для языка принимаемого ДМП-автоматом существует однозначная КС-грамматика}}
