オートマトン理論演習問題解答例

オートマトン理論演習問題解答例
2015 年 1 月 20 日分
1. (a) CFG G = ({S, T }, {a, b, c}, P, S)
P = {S → aSc | T, T → bT c | ε}
(b) P = ({q0 }, {a, b, c}, {a, b, c, S, T }, δ, q0 , S)
δ(q0 , ε, S)
=
(空スタックによる受理)
{(q0 , aSc), (q0 , T )}
δ(q0 , ε, T ) = {(q0 , bT c), (q0 , ε)}
δ(q0 , a, a) = {(q0 , ε)}
δ(q0 , b, b)
δ(q0 , c, c)
=
=
{(q0 , ε)}
{(q0 , ε)}
2. 教科書 p.270 の定理 6.14 に示された方法に
従うと，以下の生成規則が得られる．
× S → [q0 Zq0 ]
S
×
→ [q0 Zq1 ]
×
[q0 Aq0 ]
→ 0[q0 Aq0 ][q0 Aq0 ]
[q0 Aq0 ]
[q0 Aq1 ]
[q0 Aq1 ]
→ 0[q0 Aq1 ][q1 Aq0 ]
→ 0[q0 Aq0 ][q0 Aq1 ]
→ 0[q0 Aq1 ][q1 Aq1 ]
[q0 Aq1 ]
→ 1
[q1 Aq1 ]
→ 1
×
3. (a)
な非終端記号を含むので除去することが可
能であり，結果的に以下の文法が得られる．
S → [q0 Zq1 ]
[q0 Zq1 ] → 0[q0 Aq1 ]
[q0 Zq0 ] → 0[q0 Aq0 ]
[q0 Zq1 ] → 0[q0 Aq1 ]
×
ただし，先頭に×を記した生成規則は，無用
[q0 Aq1 ] → 0[q0 Aq1 ][q1 Aq1 ]
[q0 Aq1 ] → 1
[q1 Aq1 ] → 1
i. G1 において消去可能な変数は A, B, C である．
G′1
=
({S, A, B, C}, {a, b, c}, P1′ , S)
P1′
= {S → Ac | c, A → aA | a | BC | B | C, B → bA | b, C → cA | c}
ii. 単位対の集合は {(S, S), (A, A), (B, B), (C, C), (A, B), (A, C)} である．
G′′1
= ({S, A, B, C}, {a, b, c}, P1′′ , S)
P1′′
= {S → Ac | c, A → aA | bA | cA | a | b | c | BC, B → bA | b, C → cA | c}
(b) 生成的な記号は S, B, C であるので，まず A とそれを含む規則を除去する．除去後，到
達可能な記号は S のみであるので，B と C およびそれらを含む規則を除去する．
G′2
= ({S}, {b}, P2′ , S)
P2′
= {S → bS | b}
1
(c) G′3 = ({S, A, B, C, ⟨BaC⟩, ⟨aC⟩, ⟨a⟩, ⟨Ba⟩}, {a, b, c}, P3′ , S)
P3′ = { S → A⟨BaC⟩ | A⟨Ba⟩,
⟨BaC⟩ → B⟨aC⟩,
⟨aC⟩ → ⟨a⟩C,
⟨Ba⟩ → B⟨a⟩,
⟨a⟩ → a,
A → BC | b | c,
B → b,
C→c
}
2

Download Report