[例題解説] ε動作を含むNFA→簡形DFA への変換をわかりやすく解説

NFAをεを含まないDFAへ変換している画像 オートマトン

「ε動作を含む非決定性有限オートマトン」を「ε動作を含まない決定性有限オートマトン」
に変換する方法をわかりやすく説明したいと思います。

※この記事では
非決定性有限オートマトン→NFA
決定性有限オートマトン→DFA
と表記することがあります。

この記事でわかること
・ε動作を含むNFA→ε動作を含まないNFA に変換
・NFA→DFA に変換
・DFA→最簡形DFA に変換

オートマトンにおける 空動作(ε)

オートマトンにおける空動作(ε-動作)とは、
有限オートマトン(特に非決定性有限オートマトン、NFA)における遷移の一種で、
入力文字列を消費せずに状態が遷移する動作を指します。

例えば、下の図のようなオートマトンを
「ε動作を含む非決定性有限オートマトン」と言います。

図を見てわかるとおり、
状態q0からε動作でq1、q2に遷移していることがわかります。
このε動作はNFAのみで見られます。
ですので、この状態遷移図は「ε動作を含むNFA」となります。

             ε動作を含むNFA

本記事は、この状態遷移図のε動作を含むNFAを
最簡形のDFAへと変換させる方法を解説します。

変換の流れ

「ε動作を含むNFA」から「ε動作を含まないNFA
          ↓
「ε動作を含まないNFA」から「DFA
          ↓
DFA」から「最簡形DFA

「ε動作を含むNFA」から「ε動作を含まないNFA」

「ε動作を含むNFA」から「最簡形のDFA」への変換を目指しますが、
まずは、「ε動作を含むNFA」から「ε動作を含まないNFA」に変換させます。
使用する例題は↓となります。

まず、最初に行うことは
状態遷移図 を ε動作を含まない状態遷移表 で表す
ということです。

状態遷移図から状態遷移表へと変換する方法は
↓の記事でくわしく解説しておりますので、ぜひご覧ください。

実際に、ε動作を含まない状態遷移表はこのようになります。

q0は入力a,入力bが直接明記されていませんが、
q0からε動作でq1、q3へ遷移しています。
これは入力されていなくても、そこに遷移することができるということなので、
実質q0はq1、q3になれるという意味でもあります。
q1はaが入力されるとq1へ遷移して、bが入力されるとq2へ遷移します。
q3はaが入力されるとq4へ遷移して、bが入力されるとq3へ遷移します。
つまり、
q0はaが入力されるとq1、q4へ遷移して、bが入力されるとq2、q3へ遷移します。

q1,q2,q3,q4に関しては、
ε動作がないので、シンプルに入力a・入力bに対する遷移を考えればよいです。

q5はε動作があります。
q5からε動作でq3へ遷移しています。
これは入力されていなくても、そこに遷移することができるということなので、
実質q5はq3にもなれるという意味でもあります。
q5はaが入力されるとq4へ遷移して、bが入力されても遷移なし。
q3はaが入力されるとq4へ遷移して、bが入力されるとq3へ遷移します。
つまり、
q5はaが入力されるとq4へ遷移して、bが入力されるとq3へ遷移します。

これらの情報を表にまとめると、上の状態遷移表となります。
できた状態遷移図を確認してみます。
すると、q3とq5が同じ動きをしていることがわかります。
どちらも、aが入力されるとq4へ遷移し、bが入力されるとq3へ遷移します。
このような場合は、どちらかの状態にまとめることができます。
今回はq5をq3に置き換えます。
どちらも同じ動きをするので、問題はありません。
状態遷移表でq5となっているところをq3と修正するだけです。

この状態遷移表だと、q4が修正されます。
q4にaが入力されたらq3、q5へ遷移するところを、
aが入力されたらq3へ遷移すると修正します。

また、q5がq3へ置き換えられるので、
q5の情報を削除して問題ありません。

修正すると、↓のような状態遷移図となります。
これは、「ε動作を含まないNFA」です。

「ε動作を含まないNFA」から「DFA」

※以降、「ε動作を含まないNFA」を「NFA」と表記します。

NFAでは1つの入力に対して複数の状態に遷移することができますが、
DFAでは1つの入力に対して1つの状態にしか遷移しません。
そのため、NFAの状態遷移表における遷移先を1つのまとまり(状態の集合)として考えます。このまとまりがDFAの1つの状態として扱います。

NFAの現在の遷移先の状態集合に入力されたときに、到達可能なすべての状態の集合を計算し、それをDFAの遷移先とします。この操作をすべての状態と入力について繰り返すことで、DFAの状態遷移表を埋めます。

NFA→DFAへの変換については、
↓の記事でくわしく解説しておりますので、ぜひご覧ください。

実際にこのNFAからDFAへの変換を考えていきます。
NFAの初期状態「q0」を考えます。
状態「q0」はaが入力されると状態「q1,q4」に遷移します。
状態「q0」はbが入力されると状態「q2,q3」に遷移します。

ということで、次に着目すべきは生成された状態「q1,q4」と状態「q2,q3」となります。

状態「q1,q4」を考えます。
状態「q1,q4」は「q1」と「q4」の集合となります。
つまり、状態「q1」と状態「q4」の入力に対する遷移先の集合が
状態「q1,q4」の遷移先となります。

状態「q1」はaが入力されると状態「q1」に遷移します。
状態「q4」はaが入力されると状態「q3」に遷移します。
したがって、
状態「q1,q4」はaが入力されると「q1,q3」へ遷移します。

状態「q1」はbが入力されると状態「q2」に遷移します。
状態「q4」はbが入力されると状態「q4」に遷移します。
したがって、状態「q1,q4」はbが入力されると「q2,q4」へ遷移します。

状態「q1,q4」は
aが入力されると状態「q1,q3」へ遷移。
bが入力されると状態「q2,q4」へ遷移することがわかります。
また、状態「q1」「q4」が受理状態だったので、その性質を継承して
状態「q1,q4」は受理状態となります。

次は、さきほど状態「q0」で生成されていた、状態「q2,q3」を考えます。
同様に状態「q2」と状態「q3」の集合として考えると、
状態「q2,q3」は
aが入力されると状態「q2,q3」へ遷移。
bが入力されると状態「q2,q4」へ遷移することがわかります。

状態「q1,q4」で生成されていた、状態「q1,q3」を考えます。
状態「q1,q3」は
aが入力されると状態「q1,q4」へ遷移。
bが入力されると状態「q2,q3」へ遷移することがわかります。
また、状態「q1」が受理状態となっていたので、その性質を継承して
状態「q1,q3」は受理状態となります。

状態「q1,q4」で生成されていた、状態「q2,q4」を考えます。
状態「q2,q4」は
aが入力されると状態「q2,q3」へ遷移。
bが入力されると状態「q1,q4」へ遷移することがわかります。
また、状態「q4」が受理状態となっていたので、その性質を継承して
状態「q1,q4」は受理状態となります。

※以降、状態「q1,q4」などは状態「q1q4」と表記します。
(統一していれば問題がないため)

このようにして、生成された状態の遷移先をすべて状態遷移表にいれます。
すると、DFAの状態遷移表が完成しています。

「DFA」から「最簡形DFA」

最簡形DFAとは、
与えられた言語を受理する全てのDFAの中で最も少ない状態数を持つDFAのことを指します。
最簡形の作成方法は次の通りです。

〇最簡形を求める手順
1.状態を2つのグループに分る
    ↓
2.グループを細分化
    ↓
3.細分化できなくなるまで続ける
    ↓
4.同値状態をまとめる

DFA→最簡形のDFAへの変換については、
↓の記事でくわしく解説しておりますので、ぜひご覧ください。

今回のDFAを確認します。

※DFAから最簡形DFAへの変換の前に
このDFAの状態遷移表を見てみると、
「q0」と「q1q3」の遷移先が一緒であることが分かります。
また、「q0」が遷移先として出てきていません。
この場合は、一つにまとめることか可能です。
「q0」を「q1q3」に置き換えます。

ただ、
「q0」は初期状態
「q1q3」は受理状態 となっているので、
「q0」を「q1q3」に置き換える場合は
「q1q3」を初期状態・受理状態に修正する必要があります。

状態遷移表から「q0」が無くなり、シンプルになったところで
DFAから最簡形DFAへの変換工程を進めていきたいと思います。

〇最簡形を求める手順
1.状態を2つのグループに分る
2.グループを細分化
3.細分化できなくなるまで続ける
4.同値状態をまとめる

1.状態を2つのグループに分ける
DFAの状態遷移表にある状態をグループ分けします。
最初は「非受理状態」か「受理状態」の2つのグループにわけます。
今回の場合は
「非受理状態」:「q2q3」
「受理状態」:「q1q4」、「q1q3」、「q2q4」です。

2.グループを細分化
細分化する方法は、ある入力で遷移する先が異なるグループに属する場合、その状態を別のグループに分けるという分け方です。

まずは、非受理状態グループから確認していきます。
非受理状態グループは「q2q3」のみ。
したがって、これ以上細分化することができないので、終了です。

次は受理状態グループを確認していきます。
受理状態グループは「q1q4」、「q1q3」、「q2q4」の3つです。
「q1q4」は
aが入力されると「q1q3」(受理状態グループ)に遷移します。
bが入力されると「q2q4」(受理状態グループ)に遷移します。

「q1q3」は
aが入力されると「q1q4」(受理状態グループ)に遷移します。
bが入力されると「q2q3」(非受理状態グループ)に遷移します。

「q2q4」は
aが入力されると「q2q3」(非受理状態グループ)に遷移します。
bが入力されると「q1q4」(受理状態グループ)に遷移します。

それぞれ、別グループへの遷移先となっているので別のグループ同士ということです。

「q2q3」、「q1q4」、「q1q3」、「q2q4」はそれぞれ別のグループであるので、
最簡形DFAの作成工程の
「3.細分化できなくなるまで続ける」
「4.同値状態をまとめる」
は今回省けます。


これが最簡形DFAの状態となります。
つまり、今回の場合はDFAから最簡形DFAへの変換で変化はありません。
この最簡形DFAを状態遷移図にしてみます。




コメント

タイトルとURLをコピーしました