有限オートマトン
ゆうげんおーとまとん概念
状態と遷移で振る舞いを表す計算モデル。字句解析やプロトコル設計など、幅広い場面の土台となる。
年表
1955ジョージ・H・ミーリーが「A Method for Synthesizing Sequential Circuits」をBell System Technical Journal誌(Vol.34, Issue 5)に発表
概要
「状態」と、状態から状態への「遷移」の組み合わせで、システムの振る舞いを表現する計算モデル。今どの状態にいるかと、そこに入ってくる入力（信号）によって、次にどの状態へ移るかが決まる。字句解析やプロトコルの設計、デジタル回路の設計など、幅広い場面の土台になっている。
種類・系譜
有限オートマトンには大きく分けて2つの代表的な型があるとされる。1955年、ベル研究所のジョージ・H・ミーリーが「A Method for Synthesizing Sequential Circuits」という論文をBell System Technical Journal誌に発表し、後に「ミーリーマシン」と呼ばれる型の合成手法を示した（もう一方の代表格とされる「ムーアマシン」との技術的な違いの詳細は本ドラフトでは未確認。下記参照）。
関連項目
- 再帰処理が自分自身を呼び出す考え方。木構造の探索や分割統治など、簡潔で強力なアルゴリズムを生む。