有限オートマトンとは（全体像）
有限オートマトンは、「いまの状態」と「入力」から「次の状態」が決まる、簡単な機械の数学モデルのこと。自動販売機（お金を入れる→「購入できる状態」に変わる）のように、状態が移り変わるしくみを表す。
部品（構成要素）はいくつかあるが、ざっくり「状態の集まり・入力の種類・状態の移り方・スタート・ゴール（受理状態）」でできていると押さえればいい。
ここで2つのタイプに分かれる。
- DFA（決定性） … いまの状態と入力が決まれば、次の状態が1つに決まる。
- NFA（非決定性） … 同じ状態・入力でも、次の状態が複数あり得る（何も入力せず移る「空の遷移」もOK）。
詳しく：DFAとNFAの違いと等価性だけ覚えれば戦える
ここが記事の心臓部。まずはDFAとNFAの違い。
DFAとNFAの違い
| DFA（決定性） | NFA（非決定性） | |
|---|---|---|
| 次の状態 | 1つに決まる | 複数あり得る |
| 空の遷移 | なし | あり（何も入力せず移れる） |
| 作りやすさ | 動きが追いやすい | 設計が柔軟 |
DFAは「迷わず1本道」、NFAは「枝分かれもあり得る」イメージ。設計はNFAのほうが書きやすいことが多い。
ここがいちばん大事なのだが、DFAとNFAは表現力が同じ（等価）。つまり「NFAでしか表せない言語」は存在せず、どんなNFAも、同じ働きをするDFAに変換できる（ただし状態の数は増えることがある）。「NFAのほうが強力」と思い込まないのがポイントだ。
さらに、これらは正規表現とも等価。
等価なものたち
| 等価な3つ | 位置づけ |
|---|---|
| DFA・NFA・正規表現 | すべて同じ「正規言語」を扱う（チョムスキー階層のいちばん下） |
つまり「DFA＝NFA＝正規表現」で、どれも同じ範囲の文字列パターンを表せる。用途は、コンパイラの字句解析（単語の切り出し）、通信プロトコルの状態管理、文字列のパターンマッチングなど。
わかりやすく言い換えると
要するに、有限オートマトンは「状態が切り替わる機械」だ。
①DFA … 自動ドアのように「センサーが反応したら開く」と、次がきっちり1つに決まる
②NFA … 「この入力なら、こっちにもあっちにも進める」と枝分かれがあり得る
大事なのは、枝分かれできるNFAでも、表せる範囲はDFAと同じだということ。見た目は違っても、できることは同じ——だから「NFAのほうが強い」わけではない、というわけだ。
試験のツボ
🔴 一番出る：DFAとNFAの違いと等価性
①DFA＝次の状態が1つに決まる
②NFA＝次の状態が複数あり得る（空の遷移もOK）
③表現力は同じ（NFAはDFAに変換できる）
🔴 次に出る：正規表現との等価性
①DFA＝NFA＝正規表現（すべて正規言語）
②チョムスキー階層のいちばん下にあたる
🟡 押さえると安定：用途
①コンパイラの字句解析（単語の切り出し）
②プロトコルの状態管理・パターンマッチング
よくある間違い
①「NFAのほうがDFAより表現力が高い（強力）」→ ✗ 両者は等価。NFAはDFAに変換でき、表せる範囲は同じ。
②「有限オートマトンはチューリング機械と同じで、何でも計算できる」→ ✗ 有限オートマトンは記憶（テープ）を持たず、扱える範囲は正規言語に限られる。
③「DFAは同じ入力でも次の状態が複数に分かれることがある」→ ✗ DFAは次の状態が1つに決まる。複数あり得るのはNFA。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（DFAとNFAの違い）
DFAとNFAの違いに関する次の記述のうち、正しいものはどれか。
- DFAは同じ入力でも次の状態が複数に分かれ、NFAは1つに決まるものである
- DFAは次の状態が1つに決まり、NFAは次の状態が複数あり得るものである
- DFAもNFAも次の状態は必ず複数に分かれ、両者に違いはないとされている
- DFAは記憶用の無限テープを持ち、NFAはテープを持たないものである
解答は 2 だぜ。
DFAは次の状態が1つに決まり、NFAは複数あり得る（空の遷移もOK）。「Dは決まる（決定性）、Nは複数あり得る（非決定性）」と覚えとけ。
選択肢1はDFAとNFAが逆。選択肢3は「両者に違いがない」が誤り。選択肢4は「無限テープ」でチューリング機械の話だぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | DFAとNFAが逆 |
| 2 | ✓ | DFA＝1つに決まる・NFA＝複数あり得る |
| 3 | ✗ | 両者に違いがある |
| 4 | ✗ | 無限テープはチューリング機械 |
オリジナル問題2（等価性）
DFAとNFAの表現力に関する次の記述のうち、正しいものはどれか。
- NFAはDFAより表現力が高く、NFAでしか表せない言語が必ず存在している
- DFAはNFAより表現力が高く、DFAでしか表せない言語が必ず存在している
- DFAとNFAはまったく無関係で、互いに変換することはできないものである
- DFAとNFAは表現力が同じで、どんなNFAも同じ働きのDFAに変換できる
解答は 4 だぜ。
DFAとNFAは表現力が同じ（等価）で、どんなNFAも同じ働きをするDFAに変換できる（状態数は増えることがある）。「NFAのほうが強い」と思い込むなよ。
選択肢1は「NFAのほうが強力」が誤り。選択肢2は「DFAのほうが強力」が誤り。選択肢3は「無関係・変換できない」が誤りだぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | NFAが強いわけではない |
| 2 | ✗ | DFAが強いわけでもない |
| 3 | ✗ | 互いに変換できる |
| 4 | ✓ | 等価でNFA→DFA変換が可能 |
オリジナル問題3（用途と位置づけ）
有限オートマトンの用途や位置づけに関する次の記述のうち、正しいものはどれか。
- 有限オートマトンは正規表現と等価で、コンパイラの字句解析の段階で使われる
- 有限オートマトンは正規表現とは無関係で、文字列処理には使えないものである
- 有限オートマトンは無限の記憶を持ち、どんな計算でも行える万能の機械である
- 有限オートマトンは数学の理論専用で、実際のソフトウェアでは使われていない
解答は 1 だぜ。
有限オートマトンは正規表現と等価で、コンパイラの字句解析（単語の切り出し）やパターンマッチングなどに使われている。
選択肢2は「正規表現と無関係」が誤り。選択肢3は「無限の記憶・万能」が誤り（記憶を持たない）。選択肢4は「実際には使われない」が誤りだぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 正規表現と等価・字句解析で使う |
| 2 | ✗ | 正規表現と等価な関係がある |
| 3 | ✗ | 記憶を持たず万能ではない |
| 4 | ✗ | 実務で広く使われる |
まとめ
押さえどころ
- 🔴 DFAとNFA ＝ DFAは次の状態が1つに決まる、NFAは複数あり得る（空の遷移もOK）。
- 🔴 等価性 ＝ DFA＝NFA＝正規表現。NFAは同じ働きのDFAに変換できる（NFAが強いわけではない）。
- 🟡 用途 ＝ コンパイラの字句解析・プロトコルの状態管理・パターンマッチング。
次に学ぶ
- 正規表現 ── 有限オートマトンと等価な、文字列パターンの書き方。理論（オートマトン）と記法（正規表現）が結びつく。
- チョムスキー階層 ── 有限オートマトンが扱う「正規言語」が、言語全体のどこに位置するかを示す体系。理論の全体像が見える。
執筆: SikakuQuest編集部