Дерево левых выводов: различия между версиями

Версия от 16:53, 14 октября 2009

Дерево левых выводов (Left-derivation tree) - дерево, определяемое для контекстно-свободной грамматики следующим образом: корню дерева поставлена в соответствие цепочка, состоящая из единственного начального символа; если цепочка [math]\displaystyle{ \alpha }[/math] сопоставлена с некоторой вершиной [math]\displaystyle{ p }[/math] дерева, то для каждой цепочки [math]\displaystyle{ \beta }[/math], получаемой левой подстановкой из [math]\displaystyle{ \alpha }[/math], заводится вершина дерева и объявляется преемником вершины [math]\displaystyle{ p }[/math].

Литература

[Касьянов-Поттосин],

[Евстигнеев-Касьянов/94]

@@ Строка 1: / Строка 1: @@
-'''Дерево левых выводов''' (''Left-derivation tree'') -
+'''Дерево левых выводов''' (''[[Left-derivation tree]]'') - [[дерево]], определяемое для ''[[контекстно-свободная грамматика|контекстно-свободной грамматики]]'' следующим образом: [[корень|корню]] дерева поставлена в соответствие [[цепочка]], состоящая из единственного начального символа; если цепочка <math>\alpha</math> сопоставлена с некоторой [[вершина|вершиной]] <math>p</math> дерева, то для каждой цепочки <math>\beta</math>, получаемой левой подстановкой
-дерево, определяемое для ''контекстно-свободной грамматики'' следующим образом: корню дерева поставлена в
+из <math>\alpha</math>, заводится вершина дерева и объявляется [[преемник вершины|преемником вершины]] <math>p</math>.
-соответствие
-цепочка, состоящая из единственного начального символа; если
-цепочка <math>\alpha</math> сопоставлена с некоторой вершиной <math>p</math> дерева,
-то для каждой цепочки <math>\beta</math>, получаемой левой подстановкой
-из <math>\alpha</math>, заводится вершина дерева и объявляется
-преемником вершины <math>p</math>.
 ==Литература==
 [Касьянов-Поттосин],
 [Евстигнеев-Касьянов/94]

Дерево левых выводов: различия между версиями

Версия от 16:53, 14 октября 2009

Литература

Навигация

Поиск