Математическая теория формальных языков
Деревья вывода
Определение 7.1.1.
Выводам в контекстно-свободной грамматике соответствуют так называемые деревья вывода (деревья разбора, derivation tree, parse tree) - некоторые упорядоченные деревья, вершины которых помечены символами алфавита . Корень дерева отвечает начальному символу. Каждому символу слова w1, на которое заменяется начальный символ на первом шаге вывода, ставится в соответствие вершина дерева, и к ней проводится дуга из корня. Полученные таким образом непосредственные потомки корня упорядочены согласно порядку их меток в слове w1. Для тех из полученных вершин, которые помечены символами из множества N, делается аналогичное построение, и т. д.
Кроной (yield) дерева вывода называется слово, записанное в вершинах, помеченных символами из алфавита .
Пример 7.1.2.
Рассмотрим контекстно-свободную грамматику
Выводу
соответствует следующее дерево вывода.
Крона этого дерева вывода - ababab.
Упражнение 7.1.3. Перечислить все деревья вывода в грамматике
Упражнение 7.1.4. Существует ли праволинейная грамматика без -правил, в которой некоторое слово имеет бесконечно много выводов?
