有限状態機械アニメーター

有限オートマトンは固定された記憶——その状態集合——しか持ちません。入力文字列がどれほど長くても、マシンが使う記憶量は状態数を超えることはありません。だからこそDFAは無制限に数を数えることができないのです。任意の整数を「記憶」する状態は存在しません。反復補題はこれを厳密に示します。DFAが受理する十分に長い文字列は、中間部分を任意の回数繰り返しても受理されたままです。反復できない言語（aとbの個数が等しいaⁿbⁿなど）にはプッシュダウンオートマトンやチューリングマシンが必要です。マイヒル-ネロードの定理は正確な最小値を与えます——状態数は入力接頭辞の区別可能な同値類の数に等しくなります。

決定性有限オートマトンとは、状態を矢印でつないだラベル付きの図にすぎません。どの状態でも、どの入力記号に対しても、たどる矢印はちょうど一本だけなので、選択の余地はありません。機械は文字列を左から右へ一度だけ読み、最後に一つの状態にたどり着きます。その最終状態が受理状態と印されていれば、その入力はその言語に属します。矢印に沿ってトークンを滑らせるだけでたどれる——このツールが見せてくれるのは、まさにそれです。

有限オートマトンは計算機科学から始まったのではありません。1943年、ウォーレン・マカロックとウォルター・ピッツはニューロンを互いに配線された単純なオン/オフの素子として記述し、これが有限状態機械の最初の数学的モデルとなりました。1951年、スティーブン・クリーネはそうした『神経網』がどんなパターンを認識できるかを分析し、それを正規事象と名づけました——今日の正規表現の起源です。つまり、あなたがここで一歩ずつたどっているオートマトンは、脳がどう計算するかを説明しようとした試みの直系の子孫なのです。