Дерево редукций: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Дерево редукций''' (''Reduction tree'') - дерево, определяемое для заданных цепочки ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Дерево редукций''' (''Reduction tree'') - | '''Дерево редукций''' (''[[Reduction tree]]'') - [[дерево]], определяемое для заданных [[цепочка|цепочки]] <math>\alpha</math> и ''[[контекстно-свободная грамматика|контекстно-свободной грамматики]]'' следующим образом: [[корень|корню]] дерева соответствует цепочка <math>\alpha</math>; если с некоторой [[вершина|вершиной]] <math>p</math> сопоставлена цепочка <math>\beta</math>, то для каждой возможной редукции <math>\beta</math> заводится новая вершина --- | ||
дерево, определяемое для заданных цепочки <math>\alpha</math> и ''контекстно-свободной грамматики'' следующим образом: корню | [[преемник вершины]] <math>p</math>, которой и ставится в соответствие цепочка, получаемая в результате этой редукции. | ||
дерева соответствует цепочка <math>\alpha</math>; если с некоторой | |||
вершиной <math>p</math> сопоставлена цепочка <math>\beta</math>, то для каждой | |||
возможной редукции <math>\beta</math> заводится новая вершина --- | |||
преемник вершины <math>p</math>, которой и ставится в соответствие | |||
цепочка, получаемая в результате этой редукции. | |||
==Литература== | ==Литература== | ||
[Касьянов-Поттосин], | [Касьянов-Поттосин], | ||
[Евстигнеев-Касьянов/94] | [Евстигнеев-Касьянов/94] | ||
Версия от 17:12, 14 октября 2009
Дерево редукций (Reduction tree) - дерево, определяемое для заданных цепочки [math]\displaystyle{ \alpha }[/math] и контекстно-свободной грамматики следующим образом: корню дерева соответствует цепочка [math]\displaystyle{ \alpha }[/math]; если с некоторой вершиной [math]\displaystyle{ p }[/math] сопоставлена цепочка [math]\displaystyle{ \beta }[/math], то для каждой возможной редукции [math]\displaystyle{ \beta }[/math] заводится новая вершина --- преемник вершины [math]\displaystyle{ p }[/math], которой и ставится в соответствие цепочка, получаемая в результате этой редукции.
Литература
[Касьянов-Поттосин],
[Евстигнеев-Касьянов/94]