NDFAからDFAへの変換
問題文
しましょう X = (Qx, ∑, δx, q0, Fx)言語L（X）を受け入れるNDFAであること。同等のDFAを設計する必要がありますY = (Qy, ∑, δy, q0, Fy) そのような L(Y) = L(X)。次の手順では、NDFAを同等のDFAに変換します-
アルゴリズム
Input − NDFA
Output −同等のDFA
Step 1 −指定されたNDFAから状態テーブルを作成します。
Step 2 −同等のDFAの可能な入力アルファベットの下に空白の状態テーブルを作成します。
Step 3 − DFAの開始状態をq0でマークします（NDFAと同じ）。
Step 4-国{Qの組み合わせを見つける0、Q 1、...、Q nはそれぞれの可能な入力アルファベットのために}。
Step 5 −入力アルファベット列の下に新しいDFA状態を生成するたびに、ステップ4を再度適用する必要があります。それ以外の場合は、ステップ6に進みます。
Step 6 − NDFAの最終状態のいずれかを含む状態は、同等のDFAの最終状態です。
例
次の図に示すNDFAについて考えてみましょう。
| q | δ（q、0） | δ（q、1） |
|---|---|---|
| a | {a、b、c、d、e} | {d、e} |
| b | {c} | {e} |
| c | ∅ | {b} |
| d | {e} | ∅ |
| e | ∅ | ∅ |
上記のアルゴリズムを使用して、同等のDFAを見つけます。DFAの状態テーブルを以下に示します。
| q | δ（q、0） | δ（q、1） |
|---|---|---|
| [a] | [a、b、c、d、e] | [d、e] |
| [a、b、c、d、e] | [a、b、c、d、e] | [b、d、e] |
| [d、e] | [e] | ∅ |
| [b、d、e] | [c、e] | [e] |
| [e] | ∅ | ∅ |
| [c、e] | ∅ | [b] |
| [b] | [c] | [e] |
| [c] | ∅ | [b] |
DFAの状態図は次のとおりです。
