今日はε動作を除去して、ε動作のない非決定性有限オートマトンに変換する方法を解説します。
今回は少し複雑ですが、仕組みをわかってしまえば簡単ですので、そう構えずに行きましょう
目次
Q.そもそもε動作って何？
図１と図２の二つの非決定性有限オートマトンを例にしてみました。
図１がε動作ありで、図２がε動作なしです。
ε動作とは、
入力（０，１）関係なく、次の状態に遷移することができる機能です。逆流防止の効果もあります。
まあ、簡単に言えば、好きな時に次の状態に移れるようになってるよ
といった感じです。
また、あとで重要になってくるのですが、
ε動作でしか到達できない状態の集合をε閉包といいます。
図１の例だと、ｑ１とｑ２がε閉包です。
ε動作を除去する方法
今回はこのオートマトンのε動作を取り除いていきます。
ステップ１：ε動作を含む状態遷移表をかこう
はい書きました。
０の矢印の行き先、１の矢印の行き先、εの矢印の行き先を書くだけです。
ステップ２：ε動作で到達できる場所に着目した状態遷移表をかこう
ここが少しややこしいので慎重に聞いてください。
まずはεの列に着目します。ここでは、
εで到達できるすべての状態を書きます
ちなみに、自分自身の状態にもεで遷移することができます。
状態「ｑ０」を例にすると、まず自分自身「ｑ０」を書きます。
次に、εで移動できる「ｑ１」を書きます。
さらに、ｑ１から、εで「ｑ２」に到達できるので「ｑ２」を書きます。
結果「ｑ０、ｑ１，ｑ２」を書きます。
ただし、図６の状態「ｑ３」に着目した場合は
ｐ４からｑ５へはε動作でいけないので、結果は「ｑ３，ｑ４」だけになるので注意してください。
次にいつも通り「０」と「１」の遷移先を書いていきます。
「ｑ０」の状態を見ていくと、ｑ０の遷移先は「ｑ０」だけですが、「ｑ０」のε動作で到達できるのは先ほど求めた「ｑ０，ｑ１，ｑ２」なので、それを書きます。
同様に、「ｑ１」が遷移先の場合、「ｑ１」がε動作で到達できるのは「ｑ１，ｑ２」なので、「ｑ１，ｑ２」とします。
また、最後に、元のε動作を含むオートマトンの受理状態が
ε動作でしか到達できない（つまりε閉包） かつ Ø
の時、
初期状態も受理状態にします。
これで、状態遷移表の完成です。
ステップ３：ステップ２の状態遷移表から状態遷移図をかこう
ステップ２の表をもとに、状態遷移図を書いていきます。
状態「ｑ０」を例にすると、「０」での遷移先は「ｑ０，ｑ１，ｑ２」なので、それらの状態に３つの矢印を向けます。
こんな感じですべてに対してやっていけば、
ε動作を除去した非決定性有限オートマトンの完成です！
お疲れ様でした。
ここから、さらに非決定性有限オートマトンを決定性有限オートマトンに変換したいところですが、その方法はこちらの記事で紹介しているので、読んでください。
まとめ
今日はε動作を除去する方法を解説しました。
今回は少しむずかしかったかもしれないので、わからないことがあれば気軽にコメントください。
今後の記事作成にも役立てたいと思います。
それとぼくが使っているこのオートマトンの教科書かなりおすすめです
