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

オートマトン・形式言語演習問題
2016 年 10 月 11 日
1. 次の (a)∼(d) の DFA と 2 つの文字列 w1 ,w2 について，DFA にそれぞれの文字列を
入力したときの状態遷移と，それらの文字列が受理されるか否かを答えよ．状態遷
移は，開始状態から始めて遷移する状態を順番に列挙すればよい．
(a) w1 = 100, w2 = 011
(b) w1 = 10101, w2 = 0110
状態
→ ∗q0
q1
q2
(c) w1 = 011001, w2 = 1011101
0
q1
q0
q2
1
q2
q1
q0
(d) w1 = 001011, w2 = 001000
状態
→ q0
q1
q2
∗q3
0
q1
q3
q2
q3
1
q1
q2
q2
q0
2. (a) 右の DFA は 0 と 1 をそれぞれ偶数個含む文字
列の全体集合を認識する．0 と 1 をそれぞれ奇
数個含む語の全体集合を認識するように DFA
を変更せよ．
(b) 右の DFA は 1 を 3 の倍数個含む文字列の全体
集合 L を認識する．L の補集合を認識するよう
に DFA を変更せよ．
3. Σ = {0, 1} とする．次の言語を認識する DFA を求めよ．
(a) L1 = {x ∈ Σ∗ | x は 0 から始まる }
(b) L2 = {x ∈ Σ∗ | x は 2 個以上の 0 を含む }
(c) L3 = {x ∈ Σ∗ | x は 11 で終わる }
(d) L4 = {x ∈ Σ∗ | x は部分列 100 を含む }
(e) L5 = {x ∈ Σ∗ | x 中のどの 0 についてもその直後に 2 回以上の 1 が続く }
(f) L6 = {x ∈ Σ∗ | x は 2 進数としてみたときその値が 3 で割り切れる，
または x は空列である }

Download Report