Формальные грамматики позволяют задавать языки,
представляющие множества цепочек, построенных по определенным правилам.
Используемый способ задания позволяет построить любую цепочку, принадлежащую
языку. Чтобы сделать процесс построения, называемый выводом,
наглядным, его изображают в виде графа, точнее, в виде дерева, которое
называют синтаксическим деревом или
деревом вывода. Учитывая, что вывод
любой цепочки языка, принадлежащей языку, порождаемому заданной грамматикой,
должен начинаться с начального символа, правила построения дерева можно
сформулировать так:
1) В качестве начальной вершины или корня дерева возьмем вершину, которую
обозначим начальным символом грамматики <I>;
эта вершина образует нулевой ярус дерева,
2) Если при выводе цепочки на очередном шаге используется правило грамматики
<A> ® a
и вершина, помеченная нетерминалом <A>,
расположена на ярусе с номером k-1,
то к построенному дереву нужно добавить столько вершин, сколько содержится
символов в цепочке a,
расположить эти вершины на ярусе k , обозначить их символами цепочки a
и соединить эти вершины дугами с вершиной <A>.
Результатом вывода является множество конечных узлов - листьев, которые
выписываются при обходе дерева слева - вниз - направо - вверх . Рассмотрим,
например, грамматикy Г1. 8:
Г1. 8:
Vт = {a, b}, Va = {<I>},
R = {<I> ® a<I>b,
<I> ® ab },
которая порождает язык L(Г8) = {aa...abb...b},
где а и b
повторяются по n раз,
n=1,2,...