中間テストの解答

オートマトンと言語理論
2015/11/27
中間テストの解答
1. 順に，0, 0, 1, 3, 2
2. 順に，L, L, ∅, {ϵ}, {ϵ}
3. (a) L = {w ∈ Σ∗ : w は 000 を含む }
(b) L = {w ∈ Σ∗ : w は 000 で終わる }
(c) L = {w ∈ Σ∗ : w は 0 で始まり 1 で終わる }
4. (a) {0} ◦ {0} ∪ {1} ◦ {1}
(b) Σ ◦ Σ ◦ Σ∗
(c) {1} ◦ ({0} ◦ {1})∗ ◦ {0}
5. (a) ⊆，(b) 認識，(c) DFA，(d) ⊇，(e) 正規言語
6. 偶数
7. M = (Q, Σ, δ, q0 , {q2 }), Q = {q0 , q1 , q2 }, Σ = {0, 1} で，δ は以下．
1
0
0
0
1
0
1
2
1
8. N = (Q, Σ, δ, q0 , {q2 }), Q = {q0 , q1 , q2 }, Σ = {0, 1} で，δ は以下．
0,1
0
1
1
0
9. (a) 正規言語，(b) 0i ，(c) 0j 1p 0p ，(d) p，(e) 非正規言語
1
2

Download Report