演習問題1の解答補足

演習問題1.(1) 解答例
ε
(a) NFA
i
コンパイラ教科書
第4章演習問題1 解答補足
ε
a
2
b
b
3
c
b
1
ε
4
a
5
6
f
c
ε
この問題は (a) NFA (b) DFA (c) 状態数最小のDFA を求める問
題であるが，教科書巻末の解答には (c) の図しか載っていない．
そこで，復習の参考になるように，本資料では (a), (b) の解答図，
および (c) の解答図を導くために必要な状態統合について示す．
なお，スペースの関係で問題 (1), (2), (3) のみ解答を掲載する．
(b) DFA
(a) NFA
ε
i
1
ε
a
3
f
b
ε
(b) DFA
b
a
a
i,1,3
1,2,3,4
a
b
a b
1,2,3
1,2,3,f
b
1,2,3,4,f
b
a
ε
a
i
ε
1
状態
a遷移
c遷移
i,1,3
1,2,3,4
1,2,3
1,2,3
1,2,3,4
1,2,3
1,2,3,4
1234f
1,2,3,f
1,2,3,f 1,2,3,4
1,2,3
1234f
1,2,3,f
1234f
統合
f
a
i13
b
a
c
1234
a
123
b
b
c
c
123568 a
b
c
a
1234678
a
123678
b
c遷移
3
―
1,4,5
2,6
3
―
2,6
―
1,4,5,f
f
3
―
―
1,4,5
f
―
―
―
1,4,5,f
2,6
3
―
統合
2
ε
3
a
4
b
ε
5
b
a
ε
6
7
ε
8
c
f
b
ε
状態
a遷移
b遷移
c遷移
i13
1234
123
―
123
1234
123
―
第1段階の統合（右表）
を行い，括弧内に示し
た新状態名を使って新
たに書き直した状態遷
移表が下図である．
1234
1234
123568
―
123568
1234678
123678
f
1234678
1234678
1235678
f
123678
1234678
123678
f
状態
a遷移
1235678
1234678
123678
f
i
1
i
―
f
―
―
―
1
1
3
―
2
2
3
f
1235678
b
b
ε
a
(c) 状態統合
(b) DFA
b遷移
2,6
b
b
(c) 状態
統合
a遷移
i,1,5
1,4,5,f
a
(a) NFA
4
状態
演習問題1.(3) 解答例
a
2
b
3
b
c
演習問題1.(2) 解答例
ε
a
c
2,6
a
i,1,5
a
b
1,4,5
(c) 状態
統合
f
b遷移 c遷移
3
2
3
f
f
―
―
―
統合
統合(i)
(1)
(2)
統合(3)
(f)
書き直した状態遷移表を見ると，第2
段階の状態統合が可能であることが
わかる．これらを統合した結果が，
教科書掲載の解答図と対応する．
1

Download Report