Искючим из грамматики правила, содержащие непроизводящие нетерминалы

R’={ S  b, S  C, A  e, A  Ab, C  Ca, C  d }

G1=( T, N_p, S, R’)

3. Множество достижимых символов N_r = {d,a,b,S,C}

   • N⁰={S}

   • N¹={S,b,C}, из правил S  b, S  C

   • N²={S,b,C,a,d} из правил C  Ca, C  d

   • N³={S,C,b,a,d}.

   • N_r = {d,a,b,S,C}

4. Исходная грамматика без бесполезных символов будет выглядеть следующим образом.

N’={S,C}, T’={a, b, d}, R’’={ S  b, S  C, C  Ca, C  d }

G = < T’, N’, S, R’’ >

Исключение бесполезных символов

Преобразовать КС-грамматику G = < T, N, S, R > в эквивалентную грамматику, не содержащую бесполезных символов:

2.2.1.3.   T = { a, b, c, d, e, f }, N = { A, B, C, S }, R = { S ® b, S ® C, S ® cCB, A ® e, A ® Ab, B ® Bb, B ® cB, C ® Ca, C ® Bf, C ® d };

1. множество производящих нетерминалов N_p={C,A,S}

- N⁰ = 0

• A ® e, C ® d , S ® b -> значит N¹={S,A,C}

• N² = {S,A,C}, т.к. больше нет правил вывода X®a,aÎ{ a, b, c, d, e, f ,S,A,C}

• N_p={C,A,S}