Символ Х из (N U T) назовем недостижимым в кс-грамматике G=<N,T,P,S>, если Х не появляется ни в одной выводимой цепочке.

Алгоритм 1. устранение недостижимых символов.

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

Выход: кс-грамматика G'=<N',T',P',S>, у которой

  - Л(Ж')=Л(Ж) \\совпадают языки

  - для всех Х существуют такие альфа и бета что S=>*альфаХбета

Метод:

1. V0={S}, i=1

2. Vi={X | в Р есть А::=альфаХбета и А принадлежит Vi-1}

3. if Vi!=Vi-1 then i=i+1 goto2 else N'=Vi объединение N

P' состоит из правил множества Р, содержащих только символы из Vi, G'=<N',T',P',S>

 

Алгоритм 2. Устранение бесполезных символов.

Вход: кс-грамматика G=<N,T,P,S> у которой Л(Ж) не пуст

Выход: кс-грамматика G'=<N',T',P',S>, у которой Л(Ж')=Л(Ж) и N' T' нет бесползеных символов.

 

Метод:

1. Положим N0=пустому, i=1

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

3. if Ni !=Ni-1, then i=i+1 and goto 2, else N=Ni

4. G=<(Ni пересечение N),T,P',S> где P' включается P состоит из правил множества Р, содержащих символы из N'.

5. Применив к Ж1 алгоритм устранения в кс-грамматике недостижимых символов, получим G'=<N',T',P',S>

 

На шагах 1,2,3 алгоритма 2 из Ж устраняются все нетерминалы, которые не могут порождать терминальных цепочек, затем на шаге 5 устраняются все недостижимые символы.

 

Теорема:  грамматика Ж', которую строит алгоритм 2 не содержит бесполезных символов.