Automata-theory-ndfa-to-dfa-conversion

NDFAからDFAへの変換

問題文

• X =（Q〜x〜、∑、δ〜x〜、q〜0〜、F〜x〜）*を言語L（X）を受け入れるNDFAとします。 * L（Y）= L（X）*となるような同等のDFA * Y =（Q〜y〜、,,δ〜y〜、q〜0〜、F〜y〜）*を設計する必要があります。 次の手順は、NDFAを同等のDFAに変換します-

アルゴリズム

入力-NDFA

出力-同等のDFA

• ステップ1 *-指定されたNDFAから状態テーブルを作成します。

• ステップ2 *-同等のDFAの可能な入力アルファベットの下に空白の状態テーブルを作成します。

• ステップ3 *-q0でDFAの開始状態をマークします（NDFAと同じ）。

• ステップ4 *-状態の組み合わせを見つける\ {Q〜0〜、Q〜1〜、…​ 、Q〜n〜}可能な入力アルファベットごとに。

• ステップ5 *-入力アルファベット列の下に新しいDFA状態を生成するたびに、ステップ4を再度適用する必要があります。そうでない場合はステップ6に進みます。

• ステップ6 *-NDFAの最終状態のいずれかを含む状態は、同等のDFAの最終状態です。

例

次の図に示すNDFAについて考えてみましょう。

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の状態図は次のとおりです-

DFAの状態図