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


http://mb.sparknotes.com/mb.epl?b=37&m=1205860&t=341892&w=1

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2006/07/18 01:50:36
  • 終了:2006/07/25 01:55:03

回答(1件)

id:yo-kun No.1

yo-kun回答回数220ベストアンサー獲得回数302006/07/19 16:01:17

ポイント60pt

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


返還前の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

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません