有限オートマンって何か調べてみた

auです。

プログラミング言語について勉強していると、「有限オートマン」という用語があることを知りました。

いやなんだこれと全く分からなかったので調べてみました。

有限オートマンとは

有限オートマンとは、計算機が入力を「受理」するか「拒否」するかを決めるモデルのことです。

有限オートマンでは、入力された文字や数字に対し、開始状態q0から、二重丸のqnに向かって移動していき、最終的にqnにたどり着けば「受理」そうでなければ「拒否」となります。このように、受け取る文字・状態によって遷移するモデルを「決定性有限オートマン(deterministic finite automaton)」と言います。勉強していて迷路みたいだなーと思いました。

複数の遷移がある場合は「非決定性有限オートマン(nondeterministic finite automaton)」となり、迷路がさらに複雑になっていきます。qnの状態によっては自身をループするような遷移になったり、ε(イプシロン)の場合には、入力の文字列を使用せずに遷移することがあります。

やはり図を書くべきだ・・・と思ったのですが、他の課題にも追われているので、がっつり問題を解く時に書いて深く理解しようと思います。有限オートマんは、εの出現により、凡ミスが頻発する気がしてなりません。ちゃんとプログラムを組んで、ミスがないようにしていきたいと思います。