Математическая теория формальных языков

         

Деревья вывода


Определение 7.1.1.

Выводам в контекстно-свободной грамматике соответствуют так называемые деревья вывода (деревья разбора, derivation tree, parse tree) - некоторые упорядоченные деревья, вершины которых помечены символами алфавита . Корень дерева отвечает начальному символу. Каждому символу слова w1, на которое заменяется начальный символ на первом шаге вывода, ставится в соответствие вершина дерева, и к ней проводится дуга из корня. Полученные таким образом непосредственные потомки корня упорядочены согласно порядку их меток в слове w1. Для тех из полученных вершин, которые помечены символами из множества N, делается аналогичное построение, и т. д.

Кроной (yield) дерева вывода называется слово, записанное в вершинах, помеченных символами из алфавита .

Пример 7.1.2.

Рассмотрим контекстно-свободную грамматику

Выводу

соответствует следующее дерево вывода.

Крона этого дерева вывода - ababab.

Упражнение 7.1.3. Перечислить все деревья вывода в грамматике

Упражнение 7.1.4. Существует ли праволинейная грамматика без -правил, в которой некоторое слово имеет бесконечно много выводов?



Содержание раздела