Пред.Страница   След.Страница   Раздел   Содержание

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

Определение. Грамматика называется неукорачивающей или грамматикой без аннулирующих правил, если либо  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>,
                                                                                <I> ®   $ }
Выполняя все возможные замены символа I в первом правиле грамматики, получаем четыре
правила вида:
 

<I> ® a<I>b<I>,   <I> ® ab<I>,    <I>® a<I>b,    <I>® ab .

<I> ® b<I>a<I>,    <I> ® ba<I>,    <I> ® b<I>a,    <I> ® ba.

  Пред.Страница   След.Страница   Раздел   Содержание