Главная | Обратная связь

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

 

Преобразовать КС-грамматику 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}

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

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’’ >

Исключение e-правил

Алгоритм 3.7.2.1. Построение множества укорачивающих нетерминалов.

Вход.КС-грамматика G = (N, S, P, S).

Выход.Множество укорачивающих нетерминалов: N_e = {A | A Þ⁺ e, A Î N}.

Описание алгоритма.

Построить рекурсивно множества укорачивающих нетерминалов N⁰_e, N¹_e, … , Nⁱ_e, … , следующим образом:

1. Положить N⁰_e = {A | A à e, A Î N}, i = 1.

2. Положить Nⁱ_e = N^i-1_e È {A | A à a Î P и aÎ (N^i-1_e)⁺}.

3. Если Nⁱ_e ¹ N^i-1_e, положить i = i + 1 и перейти к шагу 2.

4. Положить N_e = Nⁱ_e.

Конец алгоритма

Так как N_e Í N, число повторений шага 2 алгоритма не превышает n + 1, где n – число нетерминалов грамматики G.

Замечание

При определении множеств Nⁱ_e можно рассматривать только правила вывода, не содержащие в правых частях терминалы.

Алгоритм 3.7.2.2. Преобразование КС-грамматики с e-правилами в эквивалентную НКС-грамматику.

Вход.КС-грамматика G = (N, S, P, S).

Выход.НКС-грамматика G¢ = (N¢, S, P¢, S¢), порождающая язык L(G¢) = L(G).

Описание алгоритма.

Построить множество N_e укорачивающих нетерминалов.

Построить P¢ следующим образом:

1. Положить P¢= Æ.

2. Если A à a₀B₁a₁B₂a₂… B_ka_k Î P, где k ³ 0, B_j Î N_e (1 £j £ k) и ни один из символов цепочек a_i Î (S È N)^* (0 £ i £ k) не содержит символов из N_e, то включить в P¢ все правила вывода вида A à a₀X₁a₁X₂a₂… X_ka_k, где X_j = B_j или X = e. Если все цепочки a_i = e, то правило A à e не включать в P¢.

3. Если S Î N_e, то положить N¢ = N È {S¢} и добавить в P¢два правила: S¢ à S и S¢ à e, в противном случае N¢ = N и S¢= S.

4. Положить G¢ = (N¢, S, P¢, S¢).

Конец алгоритма

 

Пример 3.8

Преобразовать КС-грамматику G = (N, S, P, S). где N = {А, S}, S = {b, c}, P = {S à сА, S à e, А à сA, А à bA, A à e}, в эквивалентную НКС-грамматику.

Используя алгоритм 3.7.2.1, получаем: N⁰_e = {S, A}, N¹_e = {S, A}, значит N_e = N¹_e = {S, A}.

Далее, выполняя шаги алгоритма 3.7.2.2, имеем:

Шаг 1. P¢= Æ.

Шаг 2. Рассмотрим правило S à сА. Для него вновое множество правил грамматики P¢ нужно включить правила S à сA и S à с. Для правила А à сA требуется добавить в множество P¢ правила А à сA и А à с, а для правила А à bA – правила А à bA и А à b. На данном шаге алгоритма получаем P¢ = {S à сА, S à с, А à сA, А à с, А à bA, А à b}

Шаг 3. В рассматриваемой грамматике S Î N_e, поэтому в множество нетерминальных символов добавляем новый нетерминал S¢, а в множество правил P¢ —два правила: S¢ à S и S¢à e.

Окончательно имеем НКС-грамматику G¢ = ({S¢, S, A}, {b, c}, {S¢ à S, S¢à e, S à сА, S à с, А à сA, А à с, А à bA, А à b }, S¢), которая эквивалентна исходной грамматике.