非決定性有限オートマトン (NFA)から決定性有限オートマトン (DFA) への変換について教えてください。下記サイトグラフ１のNFAをDFAに変換したものがグラフ２になります。しかし変換したものが誤りのようです。どこが間違っているのか教えてください。

どなたも回答されていないようですので、やや自信はありませんが回答してみます。

返還前のNFAを見るとq2,q3からの入力0の場合の遷移先は記述されていません。つまりφに遷移します。

(φとはどんな入力に対してもそれ自身φに遷移する状態です。)

従って変換後のDFAにおいて{q1,q3},{q1,q2},{q0,q1,q2},{q1,q2,q3}からの入力0の場合の遷移先の状態にはどれもφが含まれていないので間違っています。

ですから

{q1,q3}─0→{q1,q3,φ}

{q1,q2}─0→{q1,q3,φ}

{q0,q1,q2}─0→{q1,q2,q3,φ}

{q1,q2,q3}─0→{q1,q3,φ}

となります。

{q1,q3,φ}および{q1,q2,q3,φ}からの状態遷移は

{q1,q3,φ}─0→{q1,q3,φ}

{q1,q3,φ}─1→{q1,q2,φ}

{q1,q2,q3,φ}─0→{q1,q3,φ}

{q1,q2,q3,φ}─1→{q0,q1,q2,φ}

{q1,q2,φ}および{q0,q1,q2,φ}からの状態遷移は

{q1,q2,φ}─0→{q1,q3,φ}

{q1,q2,φ}─1→{q0,q1,q2,φ}

{q0,q1,q2,φ}─0→{q1,q2,q3,φ}

{q0,q1,q2,φ}─1→{q0,q1,q2,φ}

となります。

間違っていたら御容赦を。

URLはダミーです。

http://q.hatena.ne.jp/1153155033