非決定性有限オートマトン(NFA)から決定性有限オートマトン(DFA)への変換

NFAの各集合がDFAの状態に対応するように作る

NFAがn個の有限な状態を持つとすると、DFAの状態は2^n個に収まる

実際には、初期状態から到達可能なのはおよそn個ぐらいになる

コツ

遷移先と、遷移先から\epsilonで辿れる状態を一つの状態にまとめる

複雑になると漏れがありうるので、同時に表を作ると良い

参考

[** 例として(a|b)^\ast ab(a|b)^\ast cのNFAをDFAに変換する]

これが元のNFA

ここから各状態と遷移先の表を作っていく

①

まず状態 0 から出ている矢印に注目する

a で 1 へ、 b で 2 へ、 ε で 3 へ行っているのがわかる

ここで注意することは、「 ε が出ているものは考えない」という点だ

行を状態、列を遷移先にした対応表を作る

②

さらに遷移先から ε で移動できるところも含める

例えば a で 1 へ行けたが、 1 から ε が伸び、 0 , 3 へ行けることがわかる

これを b についてもやる

③

この①と②の操作を繰り返し表を埋める

④

ここからDFAの作図に入る

NFAの図とさきほど作った対応表を見ながら作っていく

スタート地点は 0 と、 0 から ε で遷移できる状態

なので、今回は 0,3 がスタートのノードになる

⑤

0,3 から a , b , c で移動できるノードを考える

まず a のとき、表の 0/a , 3/a を確認してその和集合を1ノードにする

ここでは、 0,1,3 と 4 なので 0,1,3,4 というノードになる

b に対しても同じ様に考える

⑥この操作を繰り返して、完成

受理状態を含む状態については二重丸などにする

今回は受理状態は 9 のみなので、 9 が含まれているところを二重丸にする

これでNFAからDFAの作図ができた

通常はさらにここからDFAの状態数の最小化を行う