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