「オートマトン」、情報処理の勉強していると必ず出てきて、何となく分かったつもりになるのですが、何故かいつのまにか分からなくなってしまいます(涙)
「マトン」ってカタカナで書くと「羊」しか思い浮かばない悲しい自分もいます。。。
今回はそんな「オートマトン」をしっかり理解するために、オートマトンの定義と、実際どんな形で活用されるのか解説していきます!
オートマトンとは?
オートマトン(automaton)とは、「自動人形」という意味らしいですが、それだと何のことか分かりません...
色々な表現がありますが、以下の解釈で私は理解してます。
「コンピュータの状態、遷移をモデル化したもの」
コンピュータに外部から情報を入力した場合に、内容によって状態が変化(遷移)する様を表現したものになります。
分かり易い例だと自動販売機が良く出てきますが、これは「お金を入れる」⇒「ボタンが点灯する」⇒「ボタンを押す」⇒「商品が出てくる」という状態が遷移している仕組みです。
これを状態遷移表や状態遷移図でモデル化したものがオートマトンですね。
オートマトンの種類って?
実はオートマトンにはいくつかの種類があります。
先程の例に出てきたオートマトンは「有限オートマトン」と呼ばれているモデルです。これは代表的なオートマトンの種類で、この有限オートマトンの中にも「決定的有限オートマトン」や「非決定的オートマトン」などがあります。
有限オートマトンは状態や遷移の数が有限個で表されており、「受理」と「非受理」があります。入力が終了した際に受理状態であれば、受け付けが完了します。
反対の非受理だった場合、NGということになります。
更に、「プッシュダウン・オートマトン」や「線形拘束オートマトン」などの種類もありますが、詳しくはWikipediaでご確認ください!
大事なことはオートマトンには複数の種類がある、ということですね!
オートマトンの活用例
オートマトンがどんなところで活用されているかですが、冒頭で紹介した自動販売機の処理もそうですけど、入力された情報がルールに則っているかをチェックされるときも活用されています。
パスワードを複雑にするために「数字、大文字、小文字、記号などを全て組み合わせる」というルールがあった場合、入力された文字列がこの条件になっているかを判断するためにオートマトンが用いられていたりします。
正規表現で書かれた文字列(例えば[A -Z]*など)の判定チェックなどにもオートマトンが使われています。
下の例は入力された文字列に余分な英字や記号が入っていないかをチェックするときのオートマトンとなります。数字だけの場合に受理が成功します。
オートマトンを使うことで、プログラムが最適にできているかを確認したりすることもできるようですね。
まとめ
今回はオートマトンの意味と使い道に関して解説しました!
オートマトンのまとめ
- オートマトンとはコンピュータの状態、遷移をモデル化したもの
- オートマトンは複数の種類がある
- オートマトンは自動販売機のような状態遷移で使われたり、データの入力チェックなどに使われたりする
オートマトンという言葉から意味を想像しにくいですが、コンピュータの状態や遷移をモデル化して、入力の判定チェックなどに活用するもの、と覚えてしまえば問題ないですね。
一件複雑そうにみえる処理の流れも、オートマトンを使ってシンプルにモデル化することで、より最適な形に近付けていけますね。
家事において、食器洗いや掃除、洗濯などもオートマトンでモデル化してみると、意外と複雑な手順で家事をしていることが分かって面白いかもしれませんね。
以上です!