正規表現→NFA：式から機械が生える
正規表現を入れるとトンプソン構成で NFA（非決定性有限オートマトン）が組み上がり、文字列を流すと複数の経路が同時に光って「バックトラックの正体」が見えます。 a(b|c)*
状態
いま活性（同時並行）
受理状態
細い灰矢印 = ε（空）遷移 ／ 太い矢印 = 文字の遷移
状態数 / 遷移数
—
読んだ位置
—
同時に活性な状態
—
判定（受理 / 拒否）
—
トンプソン構成の NFA（左の開始状態 ▸ から右の二重丸 ◎ 受理状態へ）
正規表現は「文字列のパターン」を表す式です。これを機械に変換する古典的な手順がトンプソン構成。
各パーツに小さな部品を割り当て、つなげていくだけで NFA（非決定性有限オートマトン）が「生えて」きます。
部品はたった4種類 ──
文字列を流すと、NFA は「あり得る場所すべて」に同時にいるのが特徴。複数の光が同時に進み、行き止まりは消えていく ── これが、決定性のエンジンが内部でバックトラックとして行う試行錯誤の正体です。
部品はたった4種類 ──
文字（1本の遷移）／連結 AB（直列につなぐ）／選択 A|B（分岐して合流）／繰り返し A*（戻り道のついたループ）。
つなぎ目には何も読まずに進める ε遷移（空遷移）が入ります。文字列を流すと、NFA は「あり得る場所すべて」に同時にいるのが特徴。複数の光が同時に進み、行き止まりは消えていく ── これが、決定性のエンジンが内部でバックトラックとして行う試行錯誤の正体です。
いま何が起きている？
ここがポイント
- 式の構造がそのまま機械の形になる ──
|は分岐、*は戻り道つきループとして「生えて」くる。 - ε遷移（空遷移）が接着剤 ── 何も読まずに状態を移れるので、部品同士を素直につなげられる。
- NFA は「あり得る場所すべて」に同時にいる ── 黄色い光が複数同時に進むのが非決定性。1本に絞る必要がない。
- バックトラックの正体は並行探索 ── 逐次バックトラックは、この「同時に複数」を1つずつ試し直しているだけ（DFA 化はこれらを事前に1つの状態にまとめ、試し直しなしで進める）。