決定性有限オートマトン（DFA）
各入力に対して次の状態が1つに決まる、状態遷移で文字列を判定する計算モデル
🤖DFAとは
決定性有限オートマトン（DFA＝Deterministic Finite Automaton）とは、有限個の状態と、状態間を移る遷移ルールだけを使って、与えられた文字列を「受け入れる（受理）」か「受け入れない（拒否）」かを判定する、とてもシンプルな計算モデルです。「決定性」とは、今いる状態と次に読む1文字が決まれば、移る先がただ1つに確定するという意味です。
身近な例で言うと、自動販売機に似ています。「0円」「50円投入済み」「100円投入済み」といった状態があり、コインを入れる（＝入力を読む）たびに次の状態へきっちり移ります。同じ状態で同じコインを入れれば、必ず同じ状態に進みます。迷いがなく一本道で進むのがDFAの特徴です。
上のツールでプリセットを選んで入力文字列を打ち込み、▶ボタンを押すと、1文字ずつ読み込みながら現在状態（赤い丸）が移っていく様子が見られます。最後まで読み終えたとき、現在状態が受理状態（二重丸）なら「受理」、そうでなければ「拒否」と判定されます。
🔁状態遷移の仕組み
DFAは数学的には 5つの要素で定義されます。難しく見えますが、図の中身を言葉にしただけです。
・状態の集合：図の丸すべて（例: q0, q1）
・入力記号の集合（アルファベット）：使える文字（例: 0 と 1）
・遷移関数 δ：「状態と1文字」から「次の状態」を返すルール
・開始状態：読み始める前にいる状態（矢印が外から刺さっている丸）
・受理状態の集合：二重丸で描かれた、ゴールとなる状態
最重要は遷移関数 δ（デルタ）です。これは「現在の状態」と「次に読む1文字」のペアに対して、移る先の状態を必ず1つだけ対応づける関数です。記号で書くと δ(q0, 1) = q1 のように表します。
DFAが「決定的」と呼ばれる理由はここにあります。どの状態にいても、どの文字を読んでも、行き先は1通りしかないため、サイコロを振るような選択（非決定性）が一切ありません。上のツールでステップを進めると、現在状態が一本道で移っていくのが確認できます。
✅文字列受理判定
文字列の受理判定の手順は、次の3ステップだけです。
・① 開始状態に置く：まだ何も読んでいない状態からスタート
・② 左から1文字ずつ読む：読むたびに遷移関数に従って状態を移す
・③ 最後の状態を見る：全部読み終えたとき受理状態にいれば「受理」、そうでなければ「拒否」
例えば「1が偶数個なら受理するDFA」に文字列 1011 を与えると、1の個数は3個（奇数）なので、最後は受理状態にいません。よって拒否です。一方 1001 なら1が2個（偶数）で受理になります。上のツールで入力を書き換えて確かめてみてください。
「与えられた状態遷移図に文字列を通したとき、受理されるのはどれか」を確かめるときのコツは、慌てず図の上で指を動かしながら1文字ずつ追うことです。DFAが受理できる文字列の集合を正規言語と呼び、正規表現で表せる範囲とちょうど一致します。
