10

NFA から DFA への変換アルゴリズムを SO コミュニティに簡潔に説明するよりもはるかに優れた人がいるでしょうか? (できれば 500 語以内で。) 私はかつて知っていたと思っていたことを混乱させるだけの図や講義を見てきました。状態図から最初の NFA 遷移テーブルを生成することにはほぼ自信がありますが、その後、イプシロンとサブセットで DFA を失います。

1) 遷移 (デルタ) テーブルで、新しい DFA 状態を表す列はどれですか? 生成された状態の最初の列ですか?

2) 以下の例の列 0 の行 {2,3} で、状態図に関して NFA について {2,3} は何を意味しますか? (申し訳ありませんが、写真で考えなければなりません。) そして、DFA で「入力 0 のループバック」になると思いますか?

3) テーブルから DFA への取得、または結果の DFA の受け入れ状態の認識に関する簡単な「経験則」はありますか?

有限自律

delta  |  0    |  1     |
=======+=======+========+
{1}    |{1}    |{2}     |
{2}    |{3}    |{2,3}   |
{3}    |{2}    |{2,4}   |
{2,3}  |{2,3}  |{2,3,4} |
{2,4}  |{3,4}  |{2,3,4} |
{2,3,4}|{2,3,4}|{2,3,4} |
{3,4}  |{2,4}  |{2,4}   |

編集：これはドット形式の上記の表です。Regexidentを乾杯します。

digraph dfa {
    rankdir = LR;
    size = "8,5"
/*  node [shape = doublecircle]; "1";*/
    node [shape = circle];

    "1" -> "1" [ label = "0" ];
    "1" -> "2" [ label = "1" ];

    "2" -> "3"   [ label = "0" ];
    "2" -> "2_3" [ label = "1" ];

    "3" -> "2"   [ label = "0" ];
    "3" -> "2_4" [ label = "1" ];

    "2_3" -> "2_3"   [ label = "0" ];
    "2_3" -> "2_3_4" [ label = "1" ];

    "2_4" -> "2_3"   [ label = "0" ];
    "2_4" -> "2_3_4" [ label = "1" ];

    "2_3_4" -> "2_3_4" [ label = "0" ];
    "2_3_4" -> "2_3_4" [ label = "1" ];
    "3_4" -> "2_4" [ label = "0" ];
    "3_4" -> "2_4" [ label = "1" ];
}

そして、ここでレンダリングされた形式で：

レンダリングされたドット グラフ

注:この表には、状態の受け入れに関する情報が欠けているため、グラフにも含まれています。

4

3 に答える 3

12

NFA から DFA を構築する場合、基本的には、NFA がその時点で取り得る状態のセットを見つけます (NFA のシミュレーションなど)。最初に開始状態から始めて、イプシロン遷移を通じて到達できるすべての状態を見つけます。この一連の状態は、結果の DFA の開始状態を形成します。次に、この状態セットからの遷移をたどります。これらは別の NFA 状態につながる可能性があります。そのため、イプシロン入力を介して到達可能な状態が再び見つかり、新しい DFA 状態になる別の NFA 状態のセットが得られます。完了するまでこのプロセスを実行します。

ポイントは、結果として得られる DFA 状態が互換性のある古い NFA 状態のセットになることです (イプシロン遷移に関して)。これらのセットはオーバーラップする場合もありますが、エラーではありません。そして今、私はあなたの質問に答えることができます：

1) 最初の列は、新しい DFA の状態を表します。これは、特定の DFA 状態を形成する NFA 状態セットを示しています。

2) あなたの仮定は正しいです。それは、0 入力で状態 {2,3} にループバックすることを意味します。

3) DFA テーブルは、このテーブルから簡単に作成できます。州に文字で名前を付けるだけです。少なくとも 1 つの NFA 受け入れ状態を含む DFA 状態は、DFA でも受け入れ状態になります。

私が十分に明確だったことを願っています。

于 2010-12-15T15:38:58.280 に答える
4

核となるアイデアはおそらく、DFA が NFA の上に重ねられた一種の機械であることを理解することです。NFA は、ノードの数、または問題との関係の点でより単純ですが、そのルールは非常に微妙であり、完全です (正しい状態になるかどうかに関係なく)。dfa は含まれるノードの点ではるかに複雑ですが、特定の入力に対して出力状態が 1 つだけ存在するため、ルールは非常に単純です。

変換はかなり簡単です。DFA の各状態は、NFA の状態のサブセットです。DFA の開始状態は、NFA の開始状態のみを含むセットであり、DFA の受け入れ状態は、NFA の受け入れ状態を要素として持つすべての状態です。

DFA でのトランジションは、唯一のトリッキーな部分です。NFA は、特定の入力に対する出力状態が一連の状態であるため、非決定論的ですが、DFA には、対応する NFA 状態のセットが独自の状態としてあり、オートマトンがどの NFA 状態になるかを表します。したがって、出力は任意の入力に対する任意の DFA 状態の状態は、その DFA 状態のすべての NFA 状態の出力状態の 結合です。

実際の実装に関しては、DFA には、本質的に NFA の州のパワーセットである州人口があります。IE、n 個の NFA 状態に対して 2^(n)。実際には、通常ははるかに小さいですが、そのサイズを予測する一般的な方法はないため、実用的な NFA から DFA への実装では、DFA 状態に到達すると動的に生成され、キャッシュされます。一定数の状態が作成されると、使用頻度の最も低い状態が破棄され、キャッシュのサイズが制限されます。

于 2010-12-15T15:37:04.140 に答える