課題3 - Tsukuba SCORE

学類学籍番号氏名
オートマトンと形式言語 (2014/5/7)
問題 1 次の言語に対する正則表現を求めよ.
1. 0 と 1 の列で, その中の 0 の個数が 3 の倍数である列全体.
2. 0 と 1 の列で, 部分列として 11 を 2 回以上含まない列全体.
問題 2 次の DFA について考える.
1
開始
1
0
0
2
1
3
0, 1
1. 下の表を完成せよ.
k
R11
k
R12
k
R13
k
R21
k
R22
k
R23
k
R31
k
R32
k
R33
k=0 k=1
ϵ
0
1
2. 上のオートマトンに対応する正則表現を求めよ.
k=2
(00)∗
0∗ 1
0(00)∗
(00)∗
0∗ 1

Download Report