Automata-theory-dfa-minimization

DFAの最小化

Myphill-Nerode定理を使用したDFA最小化

アルゴリズム

入力-DFA

出力-最小化されたDFA

• ステップ1 *-必ずしも直接接続されていない状態のすべてのペア（Q〜i〜、Q〜j〜）のテーブルを描画します[最初はすべてマークされていません]

• ステップ2 *-Q〜i〜∈FおよびQ〜j〜∉Fまたはその逆のDFA内のすべての状態ペア（Q〜i〜、Q〜j〜）を考慮し、それらをマークします。 [ここでFは最終状態のセットです]

• ステップ3 *-状態をマークできなくなるまでこのステップを繰り返します-

マークされていないペア（Q〜i〜、Q〜j〜）がある場合、ペア\ {δ（Q〜i〜、A）、δ（Q〜i〜、A）}が何らかの入力に対してマークされている場合にマークしますアルファベット。

• ステップ4 *-マークされていないすべてのペア（Q〜i〜、Q〜j〜）を結合し、それらを縮小DFAで単一の状態にします。

例

アルゴリズム2を使用して、以下に示すDFAを最小化します。

Myphill-Nerode定理を使用したDFA最小化

• ステップ1 *-すべての状態のペアのテーブルを描画します。

	a	b	c	d	e	f
a
b
c
d
e
f

• ステップ2 *-状態ペアをマークします。

	a	b	c	d	e	f
a
b
c	✔	✔
d	✔	✔
e	✔	✔
f			✔	✔	✔

• ステップ3 *-状態ペアを一時的に緑色のチェックマークでマークしようとします。 「a」と「f」の状態に1を入力すると、それぞれ「c」と「f」の状態になります。 （c、f）はすでにマークされているため、ペア（a、f）をマークします。 ここで、「b」と「f」の状態に1を入力します。それぞれ「d」と「f」の状態になります。 （d、f）はすでにマークされているため、ペア（b、f）をマークします。

	a	b	c	d	e	f
a
b
c	✔	✔
d	✔	✔
e	✔	✔
f	✔	✔	✔	✔	✔

ステップ3の後、マークされていない状態の組み合わせ\ {a、b} \ {c、d} \ {c、e} \ {d、e}があります。

\ {c、d} \ {c、e} \ {d、e}を\ {c、d、e}に再結合できます

したがって、2つの結合状態-\ {a、b}および\ {c、d、e}が得られました

したがって、最終的な最小化DFAには、3つの状態\ {f}、\ {a、b}および\ {c、d、e}が含まれます。

Reduce DFAの状態図

等価定理を使用したDFA最小化

XとYがDFAの2つの状態である場合、これらの2つの状態を区別できない場合は、それらを結合して\ {X、Y}にすることができます。 少なくとも1つの文字列Sがある場合、δ（X、S）とδ（Y、S）の一方が受け入れ、もう一方が受け入れないという2つの状態は区別できます。 したがって、DFAは、すべての状態が区別可能な場合にのみ最小になります。

アルゴリズム3

ステップ1 *-すべての状態 *Q は2つのパーティションに分割されます-最終状態*および*非最終状態*であり、 P〜0〜で示されます。 パーティション内のすべての状態は0 ^ th ^に相当します。 カウンタ *k を取得し、0で初期化します。

ステップ2 *-kを1増やします。 P〜k〜の各パーティションについて、kで区別可能な場合、P〜k〜の状態を2つのパーティションに分割します。 このパーティションXおよびY内の2つの状態は、*δ（X、S）*および*δ（Y、S）*が（k-1）識別可能な入力 *S がある場合、k識別可能です。

• ステップ3 *-P〜k〜≠P〜k-1〜の場合、ステップ2を繰り返し、それ以外の場合はステップ4に進みます。

• ステップ4 *-k ^ th ^の同等なセットを結合し、それらを還元DFAの新しい状態にします。

例

次のDFAを考えてみましょう-

DFA

q	δ(q,0)	δ(q,1)
a	b	c
b	a	d
c	e	f
d	e	f
e	e	f
f	f	f

上記のアルゴリズムを上記のDFAに適用してみましょう-

• P〜0〜= \ {（c、d、e）、（a、b、f）}
• P〜1〜= \ {（c、d、e）、（a、b）、（f）}
• P〜2〜= \ {（c、d、e）、（a、b）、（f）}

したがって、P〜1〜= P〜2〜。

縮小DFAには3つの状態があります。 削減されたDFAは次のとおりです-

Reduceed DFA

Q	δ(q,0)	δ(q,1)
(a, b)	(a, b)	(c,d,e)
(c,d,e)	(c,d,e)	(f)
(f)	(f)	(f)