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

Алгоритм 3.7.1.1. Определение множества производящих нетерминальных символов КС-грамматики.

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

Выход. Множество производящих нетерминальных символов _p = {A | A ⁺ x, A  , x  ⁺}.

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

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

1. Положить ⁰_p = , i = 1.

2. Положить ⁱ_p = ^i-1_p  {A | A    P,   (^i-1_p  )⁺}

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

4. Положить _p = ⁱ_p.

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

Алгоритм 3.7.1.2. Определение множества достижимых символов КС-грамматики.

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

Выход. Множество достижимых символов _r = {X | S ^* X, X  (S È N), ,   (  )^*}.

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

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

1. Положить ⁰_r = {S}, i = 1.

2. Положить ⁱ_r = ^i-1_r   {X  | A  X  R и A  ^i-1_r }.

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

4. Положить _r = ⁱ_r.

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

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

Вход. КС-грамматика G = (, , P, S), для которой L(G)  .

Выход. КС-грамматика G = (¢, ¢, P¢, S), у которой L(G)   и в ¢  ¢ нет бесполезных символов.

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

1. Построить множество _p производящих нетерминалов грамматики G.

2. Положить G₁ = (_p, , P_1, S,), где P₁ состоит из правил множества P, содержащих только символы из   _p.

3. Построить множество _r достижимых символов грамматики G₁.

4. Положить G¢ = (¢, ¢, P¢, S,) , где ¢ =   _r, ¢ = _r  , а P¢ состоит из правил множества P₁ , содержащих только символы из множества _r.

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

Пример 3.7

Исключить из грамматики G = (, , P, S), где  = {А, В. С. S},  = {a, b, c}, P = {S  аС, S  А, А  сАВ, В  b, С  а}, бесполезные символы.

После выполнения шага 1 алгоритма 3.7.1.3 множество _p = {В, С, S}.

После исключения непроизводящих нетерминалов получим новую грамматику G₁ = ({В, С, S}, {a, b, с}, P, S), где P = { S  аС, В  b, С  а}.

Множество достижимых символов грамматики G₁ _r = {a, C, S}.

После исключения множества недостижимых символов из грамматики G₁ получим грамматику G¢ = ({С, S}, {a}, {S  аС, С  а}, S), L(G¢) = {aa}.

Если применить к исходной грамматике сначала алгоритм 3.7.1.2, то получим, что все символы достижимы. Множество производящих символов грамматики G₁ = {В, С, S }. После исключения непроизводящих символов из грамматики G₁ имеем G¢ = ({В, С, S}, {a, b, с}, P¢, S ), где P¢ = {S  аС, В  b, С  а}, L(G¢) = L(G) = {aa}, но грамматика G¢ содержит бесполезные символы B и b.

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

Задание.   

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производящих нетерминалов грамматики G.

2. Определим множество достижимых символов.

Новая грамматика, эквивалентная исходной имеет следующий вид:

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

T’= { a, b, c, d, f}; N’ = { S, B, C}; R’= {S  b, S  C, S cCB, B  Bb, B cB, C Ca, C  Bf, C  d }

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

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