Порождение с использованием грамматики

Правила грамматики рассматриваются как переписывающие правила, в которых переменная из левой части замещается строкой из правой части.

Пусть - КС-грамматика.

цепочка из терминалов и переменных, где .

правило грамматики .

Тогда говорят, что строка с использованием правила порождает строку .

Записываем это в виде .

Один шаг порождения заменяет любую переменную в строке телом одной из ее правых частей.

Если , то говорят, что строка , используя правила грамматики, порождает строку .

Обозначения:

порождает за один шаг;

порождает за ноль или более шагов.

Определение. Строка терминалов принадлежит языку некоторой переменной тогда и только тогда, когда .

Пример. КС-грамматика задана своими правилами

Показать, что строка терминалов принадлежит языку переменной .

Таким образом, .

Дата добавления: 2013-12-14; Просмотров: 540; Нарушение авторских прав?; Мы поможем в написании вашей работы!