有限オートマトン：状態を渡り歩く
状態グラフに入力を1文字ずつ食わせ、現在状態が光って移動 → 最後に受理／拒否が決まる仕組みを体感します。
決定性有限オートマトン（DFA）は、いくつかの状態と、文字を1つ読むたびに「次にどの状態へ行くか」を決める遷移からなる、最小の計算機械です。
入力文字列を左から1文字ずつ読み、現在状態を辺に沿って渡り歩きます。文字を読み切ったとき、現在状態が受理状態（二重丸）なら「受理（YES）」、そうでなければ「拒否（NO）」です。
プリセットを選び、文字列を入れて「実行」してみましょう。図のノードを動かしたり、辺をクリックして行き先を編集すれば、自分だけの言語も定義できます。
入力文字列を左から1文字ずつ読み、現在状態を辺に沿って渡り歩きます。文字を読み切ったとき、現在状態が受理状態（二重丸）なら「受理（YES）」、そうでなければ「拒否（NO）」です。
プリセットを選び、文字列を入れて「実行」してみましょう。図のノードを動かしたり、辺をクリックして行き先を編集すれば、自分だけの言語も定義できます。
プリセット言語（アルファベット {a, b}）
入力文字列（a / b の並び。空文字列も可）
650 ms
図の操作：ノードをドラッグで移動／辺の上の
a: や b: ラベルをクリックすると行き先が次の状態へ循環します（自作言語を定義）。
ノードの○をクリックすると受理状態（二重丸）を切り替え。
いま何が起きている？
現在状態
—
読んだ／全体
—
次に読む文字
—
判定
—
入力テープ（黄色＝今読む文字）
遷移表 δ（状態 × 文字 → 行き先）
状態遷移図（→ 開始 ・ 二重丸 = 受理 ・ 光る丸 = 現在）
ここがポイント
- DFA = (Q, Σ, δ, q₀, F) ── 状態集合 Q・アルファベット Σ・遷移関数 δ・開始状態 q₀・受理状態集合 F の5つ組で完全に決まる。
- 決定性とは、どの状態でも各文字に対し行き先がちょうど1つということ。だから同じ入力なら必ず同じ経路をたどる。
- 記憶は現在状態だけ。何文字読んだかも、過去に何を読んだかも覚えず、状態という「現在地」に情報を畳み込む。
- 受理されるのは読み切った瞬間に受理状態にいるとき。受理される文字列の全体が、その機械が認識する言語になる。