299
правок
Изменения
→Дерево разбора
|id=t01
|about=5.14
|statement=Пусть <tex>G \Gamma = (V, T, P, S)</tex> — КС-грамматика. Предположим, что существует дерево разбора с корнем, отмеченным <tex>A</tex>, и кроной <tex>w</tex>, где <tex>w \in T^{*}</tex>. Тогда в грамматике <tex>G\Gamma</tex> существует левое порождение <tex>A \Rightarrow^{*}_{lm} w</tex>
|proof=
Используем индукцию по высоте дерева.
|id=t0
|about=5.29
|statement=Для каждой грамматики <tex>G \Gamma = (V, T, P, S)</tex> и <tex>w</tex> из <tex>T^{*}</tex> цепочка <tex>w</tex> имеет два разных дерева разбора тогда и только тогда, когда <tex>w</tex> имеет два разных левых порождения из <tex>S</tex>.
|proof=
(Необходимость) Внимательно рассмотрим построение левого порождения по дереву разбора в доказательстве теоремы (5.14). В любом случае, если у двух деревьев разбора впервые появляется узел, в котором применяются различные продукции, левые порождения, которые строятся, также используют разные продукции и, следовательно, являются различными.
