Древовидная грамматика

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

Древовидная грамматика (Tree grammar) - обобщение понятия грамматики применительно к деревьям (в этом контексте часто называемым термами), отличным от цепочек (см. Древовидный язык). Соответствующим обобщением понятия регулярной грамматики является регулярная древовидная грамматика. Продукции имеют вид

[math]\displaystyle{ A \longrightarrow t, }[/math],

где [math]\displaystyle{ A }[/math] --- нетерминальный символ, [math]\displaystyle{ t }[/math] --- терм, например,

[math]\displaystyle{ S \longrightarrow h(a,g(S),b) | c. }[/math].

Такие продукции генерируют регулярный древовидный язык. Аналогично можно обобщить и понятие бесконтекстной грамматики. На этот раз нетерминальные символы сами могут быть символами функций, имеющих произвольное число аргументов.

Литература

[Словарь]