34∼35ページ
35ページ
35ページ
他の例
p
0p
2a b
p
1p
3p
4p
4a b
p
2p
2p
1p
3まず、状態付の等価性判定木を作る
他の例
p
0p
2a b
p
1p
3p
4p
4a b
p
2p
2p
1p
3まず、状態付の等価性判定木を作る
p
0p
2p
1p
3 であることが分かる他の例
p
0p
2a b
p
1p
3p
4p
4a b
p
2p
2p
1p
3q0
a b
a b
q1 q2
q0 q1
他の例
p
0p
2a b
p
1p
3p
4p
4a b
p
2p
2p
1p
3q0
a b
a b
q1 q2
q0 q1
他の例 M1とM
2が等価であることを調べると
42ページ
1 r p
0 q
決定性
決定性
42ページ
非決定性
非決定性
p
0 q
状態pから入力記号1の遷移先がない
0 t r
0 s
状態rから入力0の遷移先が複数ある
42ページ
p
0から1の遷移先がない
p
1から0の遷移先がない
非決定性有限オートマトンの例
r
0から1の遷移先が2個ある
r
1から0の遷移先がない
r
2から1の遷移先がない
42∼43ページ
42∼43ページ
非決定性
決定性
43ページ
非決定性
決定性
44ページ
非決定性
44ページ
非決定性
44ページ
非決定性
44ページ
非決定性
44ページ
非決定性
44ページ
非決定性
44ページ
非決定性
44ページ