Формальные языки


Преобразование неукорачивающих грамматик



 

Определение. Грамматика называется неукорачивающей

или грамматикой без аннулирующих правил, если либо 
1)схема грамматики не содержит аннулирующих правил, 
2)либо схема грамматики содержит только одно правило вида <I> ®

$, где <I> - начальный символ грамматики, и символ I не встречается в правых частях остальных правил грамматики.

Для грамматик, содержащих аннулирующие правила, справедливо следующее утверждение.

Утверждение. Для каждой КС-грамматики Г', содержащей аннулирующие правила, можно 
построить эквивалентную ей неукорачивающую грамматику Г, такую что L(Г')=L(Г).

Построение неукорачивающей грамматики предполагает увеличение числа правил заданной
грамматики путем построения дополнительных правил, получаемых в результате исключения
нетерминалов аннулирующих правил. Чтобы построить дополнительные правила необходимо
выполнить все возможные подстановки пустой цепочки вместо аннулирующего нетерминала во все правила грамматики. Если же в грамматике есть правило вида <I> ®

$ и символ <I> входит в правые части других правил грамматики, то следует ввести новый начальный символ <I'> и заменить правило <I> ®

$ двумя новыми правилами: <I'> ®

$ и <I'>®

<I> .
В качестве иллюстрации способа построения неукорачивающих грамматик, исключим аннулирующие  правила из следующей грамматики:

                                                       Г2. 3 :       R = { <I> ®

a<I>b<I>,


                                                                                <I> ® b<I>a<I>,




- Начало -  - Назад -  - Вперед -