このセクションでは、NFA を同等の DFA に変換する方法について説明します。 NFA では、現在の状態に特定の入力が与えられると、マシンは複数の状態に移行します。特定の入力シンボルに対して、ゼロ、1 つ、または複数の動きを含めることができます。一方、DFA では、現在の状態に特定の入力が与えられると、マシンは 1 つの状態のみに遷移します。 DFA は、特定の入力シンボルに対して 1 つの手しか持ちません。

M = (Q, ∑, δ, q0, F) が言語 L(M) を受け入れる NFA であるとします。 L(M) = L(M') となるような、M' = (Q', ∑', q0', δ', F') で表される同等の DFA が存在する必要があります。

NFA を DFA に変換する手順:

ステップ1： 最初は Q' = ϕ

itn への文字列

ステップ2： NFA の q0 を Q' に追加します。次に、この開始状態からの遷移を見つけます。

ステップ 3: Q' で、各入力シンボルの可能な状態のセットを見つけます。この状態セットが Q' にない場合は、それを Q' に追加します。

ステップ 4: DFA では、最終状態は F (NFA の最終状態) を含むすべての状態になります。

例 1:

指定された NFA を DFA に変換します。

解決： 与えられた遷移図に対して、最初に遷移テーブルを構築します。

ここで、状態 q0 の δ' 遷移を取得します。

 δ'([q0], 0) = [q0] δ'([q0], 1) = [q1] 

状態 q1 の δ' 遷移は次のように取得されます。

PowerShell の複数行コメント

 δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1] 

状態 q2 の δ' 遷移は次のように取得されます。

 δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2] 

ここで、[q1, q2] 上の δ' 遷移を取得します。

 δ'([q1, q2], 0) = δ(q1, 0) ∪ δ(q2, 0) = {q1, q2} ∪ {q2} = [q1, q2] δ'([q1, q2], 1) = δ(q1, 1) ∪ δ(q2, 1) = {q1} ∪ {q1, q2} = {q1, q2} = [q1, q2] 

状態 [q1, q2] は最終状態 q2 を含むため、最終状態でもあります。構築された DFA の遷移テーブルは次のようになります。

クリック時のjQuery

遷移図は次のようになります。

状態 q2 は到達不可能な状態であるため、状態 q2 を削除できます。

例 2:

指定された NFA を DFA に変換します。

解決： 与えられた遷移図に対して、最初に遷移テーブルを構築します。

ここで、状態 q0 の δ' 遷移を取得します。

 δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] 

状態 q1 の δ' 遷移は次のように取得されます。

 δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1] 

ここで、[q0, q1] 上の δ' 遷移を取得します。

 δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] 

同様に、

 δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] 

指定された NFA と同様に、q1 は最終状態であり、DFA では q1 が存在する場所であればどこでも、その状態が最終状態になります。したがって、DFA では、最終状態は [q1] および [q0, q1] になります。したがって、最終状態の集合 F = {[q1], [q0, q1]}。

配列ソートJava

構築された DFA の遷移テーブルは次のようになります。

遷移図は次のようになります。

私たちでも DFA の州名を変更することができます。

仮定する

 A = [q0] B = [q1] C = [q0, q1] 

これらの新しい名前を使用すると、DFA は次のようになります。