オートマトンとは何ですか？

入力記号に応じて状態が遷移する抽象的な計算モデル。正規表現エンジンやコンパイラの字句解析、ネットワークプロトコルの設計など、幅広い分野の基礎理論となっている。

オートマトンのポイントは？

「状態」「入力」「遷移規則」で構成される抽象的な計算の仕組み。有限オートマトン（DFA/NFA）は正規表現の理論的基盤になっている。コンパイラの字句解析やネットワークプロトコルの設計に活用されている。プッシュダウンオートマトンやチューリングマシンへと拡張される計算理論の出発点

【おーとまとん】

💡 入力を受けて状態が変わる、コンピュータ科学の原点となる計算モデル

📌 このページのポイント

有限オートマトンの状態遷移図イメージ

ひよこ

オートマトンって何のための理論なの？

ペンギン先生

「計算するとはどういうことか」を数学的に表現したモデルだよ。自動販売機を想像してみて。お金を入れるとボタンが押せる状態になって、ボタンを押すとジュースが出る。この「入力に応じて状態が変わる」仕組みがオートマトンなんだ

ひよこ

有限オートマトンのDFAとNFAって何が違うの？

ペンギン先生

DFA（決定性有限オートマトン）は1つの入力に対して次の状態が1つに決まる。NFA（非決定性有限オートマトン）は次の状態が複数ありえるんだ。面白いのは、両方とも認識できる言語の範囲は同じということだよ

ひよこ

正規表現とどう関係するの？

ペンギン先生

実は正規表現と有限オートマトンは等価なんだ。正規表現で書けるパターンは必ず有限オートマトンで表現できるし、逆もまた然り。だからプログラミング言語の正規表現エンジンの中では、オートマトンが動いているよ

ひよこ

有限オートマトンより強力なものもあるの？

ペンギン先生

あるよ。スタック（メモリ）を1本追加した「プッシュダウンオートマトン」は括弧の対応のような構造を扱える。さらに無限のテープを持つ「チューリングマシン」は理論上あらゆる計算が可能なんだ。これがチョムスキー階層と対応しているよ

ひよこ

おもしろい！実際のソフトウェア開発で使うことってあるの？

ペンギン先生

意識せずに使っている場面は多いよ。ゲームのキャラクターAI、通信プロトコルの状態管理、UIの画面遷移設計など、「状態遷移図」を描く場面はすべてオートマトンの考え方が基盤になっているんだ。理論を知ると設計力がぐんと上がるよ

まとめ：ざっくりこれだけ覚えればOK！

「オートマトン」って出てきたら「入力で状態が変わる計算の仕組み」と思えればだいたいOK！

📖 おまけ：英語の意味

「Automaton」＝自動装置・自動機械

💬 ギリシャ語の「automatos（自ら動くもの）」が語源で、自動販売機のように入力に対して決まった動きをする機械をイメージするとわかりやすいよ