Данную грамматику часто требуется модифицировать так, чтобы порождаемый ею язык приобрел нужную структуру.

L(G), G=<N,T,P,S>

N={E}, T={+,*,(,),a}, E - начальный символ

E::=E+E | E*E| (E) | a

Грамматика G имеет два недостатка. Прежде всего она неоднозначна из-за наличия правил Е::=Е+Е|Е*Е. Эту неоднозначность можно устранить дополнив грамматику G до G1:

G1=<N,T,P,S> N={E,B}, T={+,*,(,),a} , E-начальный символ.

Е::=Е+В|E*B|B

B::=(E)|a

Другой недостаток грамматики Ж заключается в том, что операции +,* имеют один и тот же приоритет.

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

Начнем с очевидных, но важных преобразований. В некоторых случаях КС-грамматика может содержать бесполезные символы и правила.

G1=<N,T,P,S> N={S,A}, T={a,b} , S=начальный символ

P:  S::=a;

    A::=b

Нетерминал А и терминал б не могут появиться ни в какой выводимой цепочке. Т.о. эти символы не имеют отношения к языку Л(Ж), и их можно устранить из грамматики Ж не затронув языка Л.

 

Назовем символ Х принадлежащий N U T бесполезным в КС-грамматике G=<N,T,P,S>, если в ней нет вывода S=>*wXy, где w,x,y принадлежат Т*.

Чтобы установить бесполезен ли нетерминал А, построим сначала алгоритм, выясняющий, может ли нетерминал порождать какие-либо терминальные цепочки, т.е. решающий проблему пустоты множества {w | A=>*w, w принадлежит T*}. Из существования такого алгоритма следует разрешимость проблемы пустоты для КС-грамматик.

Алгориитм 1. Непуст ли язык Л(Ж)

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

Выход: ""ДА если непуст, "НЕТ БЛЯТЬ" если иначе.

Метод: Строим множества N0,N1...

1.N0=пустому, i=1

2.Ni={A|A::=альфа принадлежит Р и альфа принадлежит(N(i-1) U T)*} U N(i-1)

3. Если Ni!=Ni-1 то i=i+1 и идем к шагу 2, иначе Nl=Ni

4.Если S принадлежит Nl то выход ДА иначе НЕТ БЛЯТЬ

 

Т.к. Nl включается N то данный алгоритм должен остановиться  самое большее после n+1 повторений шага 2.

 

Алгоритм 1 говорит "да" тогда и тоько тода когда S=>*w для некоторой цепоччки  W из T*

Следствие: для кс-рамматики Ж проблема пустоты языка Л(Ж) разрешима.