このNFAからDFAへの変換が混乱しています

Question

このNFAをDFAに変換しようとしています。私は、空の文字列のための異なる状態を設定しようとした

：

私はNFAとDFAの両方のための遷移テーブルを有しています。しかし、何をすれば元のNFAで動作しないDFAが得られます。

私はサークルで少し行きました、誰かが私が間違っていることを私に見せることができますか？

Answer 1

NFAの同等のDFAを生成するアルゴリズムは、DFAの状態のセットとして、NFAの状態のセットのパワーセットを取ります。つまり、NFAの状態がq0とq1の場合、DFAの状態は{}, {q0}, {q1}, {q0, q1}になります。 NFAがqからq'への遷移をaとすると、DFAはpからp'のaになります。ここで、p'はNFAの状態のセットに対応する状態です入力中のNFAの状態のpに対応する集合内の状態のいずれかによって到達される。a。私たちのため：

• {}はそれ自身にしかつながりません。それは死んだ状態です。遷移{}〜{}の0または1。
• {q0}は0にし、どこにも1にq0またはq1につながるq0含まれています。遷移{q0}~{q0, q1}の0と{q0}~{}の1。
• {q1}は1にし、どこにも0にq0またはq1につながるq1含まれています。遷移{q1}~{q0, q1}は0となり、{q1}~{}は1となります。
• {q0, q1}は、q0とq1の両方を含んでいます。 q0はq0に、q1は0に、q1はどこにも行きません。遷移{q0, q1)〜{q0, q1}〜0です。 q1はq0またはq1は1になり、q0はどこでもなく1になります。そのため、遷移{q0, q1}〜{q0, q1}は1です。ここ

テーブルである：

  0,1 
     / \ 
     |  | 
      \ v 
{q0} -0-> {q0,q1} <-1- {q1} 
    \     /
    \    /
    \-1--> { } <--0-/ 

注この構成では、最終的な状態は含むセットに対応するDFAのいずれかの状態であること：ここ

   0 |  1 
    {} |  {} |  {} 
    {q0} | {q0,q1} |  {} 
    {q1} |  {} | {q0,q1} 
{q0,q1} | {q0,q1} | {q0,q1} 

グラフでありますNFAの状態を受け入れる。私たちについては、受諾状態は、q0がNFAの唯一の受け入れ状態であるので、{q0}と{q0,q1}です。

また、この構成では、初期状態は、NFAの初期状態のみを含むセットに対応する状態であることにも注意してください。私たちのために、{q0}。