Назовем КС-грамматику G=<N,T,P,S> грамматикой без Е-правил если либо

1)Р не содержжит правил вида А::=E либо

2)Есть точно одно E-правило S::=E не встечается в правых частях отсальных правил из Р

 

АЛГОРИТМ1) Устранение Е-правил

Вход:КС-грамматика G=<N,T,P,S>

выход:Экиввалентная КС-грамматика G'=<N',T',P',S'>

метод: 1)Применяем шаги 1,2,3 из алгоритма устранения бесполезных символов. Определяем множество Ne= {А|A принадлежит N и A'=>E}

       2)Построить P' так:

              а) Если А::=АЛФА0*бета1*АЛФА0*БЕТА2*АЛФА2,БЕТАkАЛФАk принадлежит P, к>=0 и БЕТАi принадлежит Ne

                 для 1<=i<=k, но ни один символ в цепочках АЛФА1 (o<=j<=k) не принадлежит Ne, то включить в P' правила вида.

                 А::=АЛФА0 Х1 АЛФА1 Х2, ... АЛФАk-1 Хk АЛФАk

где х-либо БЕТАi либо Е Но не включать правило  А::=Е это могло произойти в случае если все АЛФАi равны Е

               б) если S принадлежит Ne включить в Р' правила S'::= E|S где S' - новый символ и положить N'=N U {s}

3)положить G'=<N',T',P',S'>

 

Другое полезное преобразование грамматик - устраннение правил вида A::=B которые мы будем называть цепными.

АЛГОРИТМ2)устранение цепных правил

Вход: КС-грамматика G без Е-правил

Выход: эквивалентная грамматика G' без Е-правил и без цепных правил

 

метод: 1) Для каждого  А принадлежащего N построить Na={B|A=>B} следущим образом.

a) положить N0={A} и i=1

б) Положить Ni={C|B::=C принадлежит P и В принадлежит Ni-1} U Ni-1

в) Если Ni