人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

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

●質問者: moonhappy
●カテゴリ:コンピュータ 学習・教育
✍キーワード:DFA オートマトン グラフ サイト
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● yo-kun
●60ポイント

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


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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ