Дерево левых выводов

Материал из WEGA
Версия от 13:23, 13 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Дерево левых выводов''' (''Left-derivation tree'') - дерево, определяемое для ''контекс...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

Литература

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

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