Изменения

Перейти к: навигация, поиск

ДМП-автоматы и неоднознчность

2299 байт убрано, 01:37, 5 января 2015
→‎Теоремы
{{В разработке}}
==Теоремы==
{{Теорема
|id=t0
|about=5.29
|statement=Для каждой грамматики <tex>G = (V, T, P, S)</tex> и <tex>w</tex> из <tex>T^{*}</tex> цепочка <tex>w</tex> имеет два разных дерева разбора тогда и только тогда, когда <tex>w</tex> имеет два разных левых порождения из <tex>S</tex>.
|proof=
(Необходимость) Внимательно рассмотрим построение левого порождения по дереву разбора в доказательстве теоремы (5.14). В любом случае, если у двух деревьев разбора впервые появляется узел, в котором применяются различные продукции, левые порождения, которые строятся, также используют разные продукции и, следовательно, являются различными.
(Достаточность) Хотя мы предварительно не описали непосредственное построение дерева разбора по левому порождению, идея его проста. Начнем построение дерева с корня, отмеченного стартовым символом. Рассмотрим порождение пошагово. На каждом шаге заменяется переменная, и эта переменная будет соответствовать построенному крайнему слева узлу дерева, не имеющему сыновей, но отмеченному этой переменной. По продукции, использованной на этом шаге левого порождения, определим, какие сыновья должны быть у этого узла. Если существуют два разных порождения, то на первом шаге, где они различаются, построенные узлы получат разные списки сыновей, что гарантирует различие деревьев разбора.
}}
 
 
{{Теорема
|id=t1
|about=1
|statement=Если <tex>L=N(P)</tex> для некоторого ДМП автомата <tex>P</tex>, то <tex>L</tex> имеет однозначную КС-грамматику
|proof=
{{Теорема
|id=t2
|about=2
|statement=Если <tex>L=L(P)</tex> для некоторого ДМП-автомата <tex>P</tex>, то <tex>L</tex> имеет однозначную КС-грамматику
|proof=
Kamigan4eg
299
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/43438»

Навигация