4. Устранить из кс-грамматики бесполезные символы и ε–правила.

Дана КС-грамматика L1 = {T, V, P, S0}

T = {a, b, c, d}

V = {A, B, C, F}

P = { S → b, S → CF, S→ cCB, A→ Ab, A→ c, B → cB, C→ Ca, F→ d }

S0 = {S}

Шаг 1. Удаление непроизводящих символов.

N₀ = Ø

N₁ = {S, A, F} U Ø

N₂ = {S, A, F} = N₁

Грамматика L1 имеет вид:

L′ = {{b, c, d}, {S, A, F}, { S → b, A→ Ab, A→ c, F→ d }, S}

Шаг 2. Удаление недостижимых символов из грамматики L′.

N₀ = {S}

N₁ = {S} U {b}

N₂ = {S, b} = N₁

Преобразованная грамматика L1, не содержащая бесполезные символы.

L′′₁ = {{b}, {S}, {S → b}, S}

Дана КС-грамматика L2 = {T, V, P, S0}

T = {a, b, c}

V = {S, A, B, C}

P = { S → b, S → C, S→ cCB, A→ Ab, A→ c, B → cB, C→ Ca, C→ ε }

S0 = {S}

Шаг 1. Построим множество укорачивающих нетерминалов N_ε.

N₀ = {C}

N₁ = {C} U {S}

N₂ = {C, S} = N₁

N_ε = {C, S}

Шаг 2. Устранение ε – правил.

P′ = Ø

S → C не будет входить в P′.

S→ cCB => S→ cCB, S→ cB;

C→ Ca => C→ Ca, C→ a;

S входит в N_ε => добавляем новый нетерминал S′ и правила S′ → S и S′ → ε.

Преобразованная грамматика L2, не содержащая ε–правила.

L′₂ = {{a, b, c}, {S′, S, A, B, C}, { S′ → S, S′ → ε, S→ cCB, S→ cB, S→ b, C→ Ca, C→ a, A→ Ab, A→ c, B → cB}, S′}

5. Устранить из kс-грамматики цепные правила и устранить левую рекурсию

Дана КС-грамматика L3 = {T, V, P, S0}

T = {a, b, c}

V = {A, B, C}

P = {S → b, S → C, S→ cCB, A→ Ab, A→ C, B → cB, C→ Ca, C→ b}

S0 = {S}

Шаг 1.

Ns = {S, C}

N_A = {A, C}

N_B = {B}

N_C = {C}

Шаг 2. Составление правил P′.

S: S → b, S → Ca, S→ b, S→ cAB

A: A→ Ab, A→ Ca, A→ b

B: B → cB

C: C→ Ca, C→ b

Преобразованная грамматика L3, не содержащая цепные правила.

L′₃ = {{a, b, c}, {S, A, B, C}, { S → b, S → Ca, S→ b, S→ cAB, A→ Ab,

A→ Ca, A→ b, B → cB, C→ Ca, C→ b }, S}

Дана КС-грамматика L4 = {T, V, P, S0}

T = {a, b, c}

V = {A, B, C}

P = {S → AB, S → SC, A→ BB, A→ Ab, A→ a, B → b, C→ Ca, C→ b}

S0 = {S}

1) Для правил S → AB, S → SC преобразованная грамматика будет содержать правила: S → ABS′, S′ → C, S → AB.

2) Для правил A→ BB, A→ Ab, A→ a преобразованная грамматика будет содержать правила: A→ BBA′, A′→ b, A→ aA′, A→ a, A→ BB.

3) Для правил C→ Ca, C→ b преобразованная грамматика будет содержать правила: C′→ a, C→ bC′, C→ b.

Преобразованная грамматика L4, не содержащая левую рекурсию.

L′₄ = {{a, b, c},{S, A, B, C, S′, A′, C′},{S → ABS′, S′ → C, S → AB,

A→ BBA′, A′→ b, A→ aA′, A→ a, A→ BB, C′→ a, C→ bC′, C→ b, B → b},S}

6. Определить форму кс-грамматики и сделать ее приведение.

КС – грамматика G = (V, T, P, S) называется грамматикой в нормальной форме Хомского, если каждое правило из Р имеет один из следующих видов:

1. A → BC, где A,B и C ϵ V;

2. A → a, где a ϵ T;

3. S → ε, если ε ϵ L(G), причем S не встречается в правых частях правил.

КС – грамматика G = (V, T, P, S) называется грамматикой в нормальной форме Грейбах, если в ней нет ε-правил и каждое правило из Р, отличное от

S → ε, имеет вид A → аα, где а ϵ T и α ϵ V*.

7. Спроектировать МП автомат для приведенной КС-грамматики L = {V = {S, F, L},T={i, * , :,(,)}, P = {S→(F: L), F→ L*, F→ i, L→F},S0}

MP = {Q, T, Г, δ, q0, Z0, F}

Q = {S, F, L},

T = {i, *, :, (, )},

q0 = S0.

Правила перехода δ:

δ(q, ɛ, S) = {(q, (F : L))}

δ(q, ɛ, F) = {(q, L*), (q, i)}

δ(q, ɛ, L) = {(q, F)}

δ(q, i, i) = {(q, ɛ)}

δ(q, *, *) = {(q, ɛ)}

δ(q, :, :) = {(q, ɛ)}

δ(q, (, ( ) = {(q, ɛ)}

δ(q, ), ) ) = {(q, ɛ)}

Пример разбора входной цепочки символов:

(q, (i**:i*), S) ˫ (q, (i**:i*), (F:L))

˫ (q, i**:i*), F:L))

˫ (q, i**:i*), L*:L))

˫ (q, i**:i*), L**:L))

˫ (q, i**:i*), F**:L))

˫ (q, i**:i*), i**:L))

˫ (q, **:i*), **:L))

˫ (q, *:i*), *:L))

˫ (q, :i*), :L))

˫ (q, i*), L))

˫ (q, i*), F))

˫ (q, i*), L*))

˫ (q, i*), F*))

˫ (q, i*), i*))

˫ (q, *), *))

˫ (q, ), ))

˫ (q, ɛ, ɛ)

Построение расширенного МП – автомата:

MP = {Q, T, Г, δ, q0, Z0, F}

Q = {S, F, L},

T = {i, *, :, (, )},

q0 = S0.

Правила перехода δ:

δ(q, i, ɛ) = {(q, i)}

δ(q, *, ɛ) = {(q, *)}

δ(q, :, ɛ) = {(q, :)}

δ(q, (,ɛ ) = {(q, ( )}

δ(q, ), ɛ ) = {(q, ) )}

δ(q, ɛ, (F:L) ) = {(q, S)}

δ(q, ɛ, L*) = {F}

δ(q, ɛ, i) = {F}

δ(q, ɛ, F) = {(q, L)}

δ(q, ɛ, _┴ S) = {(r, ɛ)}

Пример разбора входной цепочки символов:

(q, (i**:i*), _┴) ˫ (q, i**:i*), _┴( )

˫ (q, **:i*), _┴ (i )

˫ (q, **:i*), _┴ (F )

˫ (q, **:i*), _┴ (L )

˫ (q, *:i*), _┴ (L* )

˫ (q, *:i*), _┴ (F )

˫ (q, *:i*), _┴ (L )

˫ (q, :i*), _┴ (L* )

˫ (q, :i*), _┴ (F )

˫ (q, i*), _┴ (F: )

˫ (q, *), _┴ (F:i )

˫ (q, *), _┴ (F:F )

˫ (q, *), _┴ (F:L )

˫ (q, ), _┴ (F:L* )

˫ (q, ), _┴ (F:F )

˫ (q, ), _┴ (F:L )

˫ (q, ɛ, _┴ (F:L) )

˫ (q, ɛ, _┴S )

˫ (q, ɛ, ɛ)