こんにちは、モドくんチャンネルのもどです。
今日は情報系大学院入試を乗り越えたオートマトンマスターの私ができるだけわかりやすく解説します。
オートマトンは一見難しそうですが、パズルみたいなもんです。やり方覚えれば絶対できるようになります！
今回は非決定性有限オートマトンを決定性有限オートマトンに変換します。
目次
そもそも決定性と非決定性の違いは何？
図1が非決定性、図2が決定性です。簡潔に言うと
・非決定性：1つの状態から、0、1の矢印がいくつ出ていてもいい
・決定性 ：1つの状態から、0、1の矢印の二つが必ずある。
です。
多分これだけだとわかりにくいと思うので、図1と図2の「q1」を見てください。
図1では、q1から出てる矢印は「1」が2つ、「0」が1つの計3つ出ています。それに対し
図2では、q1から出てる矢印は「0」「1」の二つだけです。
また、q0も見て欲しいのですが、
図1では「0」の矢印しか出ていませんが、
図2では「0」と「1」の矢印が出ています。
このように、必ず0と1の行き先が一つに定まるのが決定性有限オートマトンで、そうでないのが非決定性有限オートマトンです。
実際に変換してみよう！
今回はこの非決定性オートマトンについて考えていきます。
「０・・・・１」となる文字列を含むものを受理するオートマトンですね。
ステップ１：状態遷移表を描こう
これが 図３のオートマトンを表にしたものになります。
簡単に説明しますと、「０」で移動する先の値、「１」で移動する先の値を書いていきます。
また、初期状態には矢印、受理状態には＊をつけましょう。
ステップ2：決定性オートマトンの状態遷移表を書こう！
えっいきなり、決定性？と思ったかもしれませんが、そんなに難しくないんで安心してください。
まず、状態のところにはq１、q２、q３の全ての組み合わせの状態と、何もないことを表す記号を書きます。
そして、｛q0,q1｝などの二つの状態がまとめてあるものの場合は
q０とq１の結果を合わせたものを書きます。
これを全てにおいてやっていきます。めんどくさいですが頑張りましょう。
ステップ３：ステップ２の表を使って状態遷移図を書こう
はい、書きました。ステップ１と逆の手順でやれば描けると思います。
これで、決定性有限オートマトンの状態遷移図は完成です
最初に説明した「1つの状態から、0、1の矢印の二つが必ずある。」というルールが確認できると思います。
しかし、これだとなんか状態数が多いし、わかりにくいですよね。
そのため、次からは状態数を最初にします。
ステップ４：状態数を最小にしよう！
上の表が、ステップ２で書いた決定性有限オートマトンの状態遷移表です。
よく見ると、マーカーを引いた
・(q1)と(q0,q1)の遷移先
・(q1,q2)と(q0,q1,q2)の遷移先
が同じですよね。
こういうやつは１つにまとめます。
まとめ方は
(q1)と(q0,q1)をまとめるときは、(q0,q1)に
(q1)と(q2)をまとめるときは、(q1,q2)とします。
そして、まとめ終わった状態遷移表が図７の下の表になります。
注意点として、q１のような行き先がなくなったものに関しては、合体してできたものに変更します。
ここではq１は（q０、q１）に書き換えます。
これで、表での準備は完了です。
ステップ５：状態遷移表を元に状態数最小の状態遷移図を書こう
図８の左の図がステップ４の表をそのまま書いたものです。
でもよく見ると、（q０,q2）には初期状態の（q０）から矢印の向き的に到達できないですよね。
そういうものはカットします。
カットしてできたのが、右の図になります。
これが、状態数最小の決定性有限オートマトンです。
図６と比べてだいぶスッキリしましたね。
これで完成です。
まとめ
今回は非決定性有限オートマトンから決定性有限オートマトンに変換するやり方を紹介しました。
ε動作を含む場合の変換方法も記事にしたのでこちらをご覧ください。
また僕が使っているこの本とてもわかりやすいのでおすすめです。
Youtubeで解説動画も出す予定なのでチャンネル登録お願いします。
