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

オートマトン理論演習問題解答例
2015 年 1 月 13 日分
1. (a) 構文木
S
S
S
S
S
a
a
ε
S
b
S
S
ε
a
a
ε
b
ε
(b) 最左導出
S ⇒ aS ⇒ aaSbS ⇒ aabS ⇒ aab
S ⇒ aSbS ⇒ aaSbS ⇒ aabS ⇒ aab
(c) 最右導出
S ⇒ aS ⇒ aaSbS ⇒ aaSb ⇒ aab
S ⇒ aSbS ⇒ aSb ⇒ aaSb ⇒ aab
2. (a)
(q0 , ab, Z)
⊢ (q0 , b, AZ)
(d)
⊢ (q1 , ε, Z)
⊢ (q1 , ε, ε)
(b) (q0 , aab, Z)
(c)
(q0 , aabba, Z)
(q0 , aaabbb, Z)
⊢ (q0 , aabbb, AZ)
⊢ (q0 , abbb, AAZ)
⊢ (q0 , bbb, AAAZ)
⊢ (q1 , bb, AAZ)
⊢ (q1 , b, AZ)
⊢ (q1 , ε, Z)
⊢ (q0 , ab, AZ)
⊢ (q0 , b, AAZ)
⊢ (q1 , ε, AZ)
⊢ (q1 , ε, ε)
⊢ (q0 , abba, AZ)
⊢ (q0 , bba, AAZ)
⊢ (q1 , ba, AZ)
⊢ (q1 , a, Z)
⊢ (q1 , a, ε)
1
3. (a) P = ({q0 , q1 }, {0, 1}, {A, Z}, δ, q0 , Z) (空スタック受理)
δ(q0 , 0, Z) =
δ(q0 , 0, A) =
{(q0 , AA)}
{(q0 , AAA)}
δ(q0 , 1, A)
δ(q1 , 1, A)
=
=
{(q1 , ε)}
{(q1 , ε)}
δ(q0 , ε, Z)
=
{(q0 , ε)}
(b) P = ({q}, {0, 1}, {A, Z}, δ, q, Z, {q}) (最終状態受理)
δ(q, 0, Z) =
δ(q, 0, A) =
{(q, AZ)}
{(q, AA)}
δ(q, 1, A)
{(q, ε)}
=
(c) P = ({q}, {0, 1}, {A, B, Z}, δ, q, Z) (空スタック受理)
=
=
{(q, AZ)}
{(q, BZ)}
δ(q, 0, A) =
δ(q, 1, A) =
δ(q, 0, B) =
{(q, AA)}
{(q, ε)}
{(q, ε)}
δ(q, 1, B) =
δ(q, ε, Z) =
{(q, BB)}
{(q, ε)}
δ(q, 0, Z)
δ(q, 1, Z)
2

Download Report