Процедура Раздел 2

ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ КС-ГРАММАТИК

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

Преобразовать КС-грамматику 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, b, c, d, e, f ,S,A,C}

• N_p={C,A,S}