NFAからDFAへの変換
NFAの各集合がDFAの状態に対応するように作る
NFAが$ n個の有限な状態を持つとすると、DFAの状態は$ 2^n個に収まる
実際には、初期状態から到達可能なのはおよそ$ n個ぐらいになる
コツ
遷移先と、遷移先から$ \epsilonで辿れる状態を一つの状態にまとめる
複雑になると漏れがありうるので、同時に表を作ると良い
参考
例として$ (a|b)^\ast ab(a|b)^\ast cのNFAをDFAに変換する
これが元のNFA
ここから各状態と遷移先の表を作っていく
https://gyazo.com/555e7544d4629f0ee8f1849d57039a65
①
まず状態0から出ている矢印に注目する
aで1へ、bで2へ、εで3へ行っているのがわかる
ここで注意することは、「εが出ているものは考えない」という点だ
行を状態、列を遷移先にした対応表を作る
table:対応表
a b c
0 1 2 x
②
さらに遷移先からεで移動できるところも含める
例えばaで1へ行けたが、1からεが伸び、0,3へ行けることがわかる
table:対応表
a b c
0 1,0,3 2 x
これをbについてもやる
table:対応表
a b c
0 1,0,3 2,0,3 x
③
この①と②の操作を繰り返し表を埋める
table:対応表
a b c
0 0,1,3 0,2,3 x
1 x x x
2 x x x
3 4 x x
4 x 5,8 x
5 5,6,8 5,7,8 x
6 x x x
7 x x x
8 x x 9
9 x x x
④
ここからDFAの作図に入る
NFAの図とさきほど作った対応表を見ながら作っていく
スタート地点は0と、0からεで遷移できる状態
なので、今回は0,3がスタートのノードになる
https://gyazo.com/4aedece1be37b515ca8e75a6778b341b
⑤
0,3からa,b,cで移動できるノードを考える
まずaのとき、表の0/a, 3/aを確認してその和集合を1ノードにする
ここでは、0,1,3と4なので0,1,3,4というノードになる
bに対しても同じ様に考える
https://gyazo.com/4ac89dd5d7448698f9fb3e8d2b1299c1
⑥この操作を繰り返して、完成
https://gyazo.com/0d9e7bb65b1913f9be56dfb43c90498b
受理状態を含む状態については二重丸などにする
今回は受理状態は9のみなので、9が含まれているところを二重丸にする
これでNFAからDFAの作図ができた