オートマトン・形式言語 演習問題解答例
2016 年 10 月 18 日分
1.
(a) w1 = 100: {q0 , q1 }，受理
w2 = 1011: ∅，拒否
(b) w1 = 0010: {q0 , q1 }，拒否
w2 = 0011: {q0 , q2 }，受理
2.
3.
(a)
(b)
(c)
(d)
(a) {q1 , q2 }
1
1
1
0
0
0
(b) {q0 } → {q0 , q1 } → {q0 , q1 , q2 } → {q1 , q2 } → {q1 , q2 }
(c) ∅,
1
1
{q0 } → {q0 , q1 } → {q1 } → {q2 } → ∅
4.
(a)
(b)
状態 0
1
→ {q0 } {q1 } {q0 }
∗{q1 } ∅
{q0 , q1 }
∅ ∅
∅
∗{q0 , q1 } {q1 } {q0 , q1 }
開始状態 {q0 } から到達不能な状態は省略．
状態 0
1
→ {q0 } {q1 }
{q0 }
∗{q1 } {q1 , q2 }
∅
∗{q1 , q2 } {q1 , q2 , q3 } {q2 }
∅
∅ ∅
∗{q1 , q2 , q3 } {q1 , q2 , q3 } {q0 , q2 }
{q2 }
{q2 } {q1 , q3 }
{q0 , q2 } {q1 , q3 }
{q0 , q2 }
{q0 }
∗{q1 , q3 } {q1 , q2 }
1
追加問題
教科書 p.75 問 2.3.4 (b) （アルファベットは {0, 1, . . . , 9} から {a, b, c} に変更．
）
2

オートマトン・ 形式言語 演習問題解答例

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

オートマトン・ 形式言語 演習問題解答例

オートマトン・形式言語 演習問題解答例