コンピュータ科学の広大な世界において、プログラムやシステムの動作を数学的に表現するための基礎理論が数多く存在します。

その中でも、特定の入力を受け取って内部の状態を変化させる仕組みをモデル化した「有限オートマトン」は、エンジニアにとって避けては通れない重要な概念です。

有限オートマトンは、英語で「Finite Automaton」や「Finite State Machine（FSM）」と呼ばれ、日本語では「有限状態機械」とも表現されます。

私たちの身近にある自動販売機や駅の自動改札機、さらにはプログラミング言語のコンパイラなど、至る所でこの理論が応用されています。

この記事では、有限オートマトンの基本的な仕組みから、状態遷移の考え方、決定性と非決定性の違いまでを詳しく紐解いていきます。

目次 [ close ]
  1. 有限オートマトンとは何か
  2. 有限オートマトンを構成する5つの要素
    1. 1. 状態の有限集合（Q）
    2. 2. 入力アルファベット（Σ）
    3. 3. 状態遷移関数（δ）
    4. 4. 初期状態（q0）
    5. 5. 受理状態の集合（F）
  3. 状態遷移図と状態遷移表の役割
    1. 状態遷移図による可視化
    2. 状態遷移表による管理
  4. 決定性有限オートマトン（DFA）の仕組み
  5. 非決定性有限オートマトン（NFA）の仕組み
  6. 有限オートマトンの具体例：駅の自動改札機
  7. 有限オートマトンと正規表現の深い関係
  8. プログラミングにおける実装例
  9. 有限オートマトンの限界
  10. まとめ

有限オートマトンとは何か

有限オートマトンとは、有限個の状態を持ち、入力信号に応じてそれらの状態間を遷移する抽象的な計算モデルのことです。

「有限」という言葉が示す通り、このモデルが保持できる記憶（状態）の数はあらかじめ決められた上限を超えません。

有限オートマトンは、現在の状態と外部からの入力だけを判断材料にして、次にどの状態へ移るかを決定します。

このシンプルかつ強力な性質により、複雑な論理回路やソフトウェアの振る舞いを明確に定義することが可能になります。

コンピュータはメモリを利用して情報を保持しますが、有限オートマトンはそのメモリの使用量が「一定」である特殊なマシンと見なすこともできます。

例えば、入力文字列が特定のパターンに合致するかどうかを判定する処理は、有限オートマトンの得意分野です。

有限オートマトンを構成する5つの要素

有限オートマトンを数学的に定義する場合、一般的に「5つの要素（5組）」を用いて表現されます。

これらを理解することで、どのような複雑なシステムも論理的な枠組みの中に落とし込むことができます。

1. 状態の有限集合（Q）

オートマトンが取り得るすべての状態をまとめたグループです。

例えば「停止中」「動作中」「待機中」といった個別の状況がこれに該当します。

2. 入力アルファベット（Σ）

マシンが受け取ることのできる記号や信号の集合です。

デジタル回路であれば「0」と「1」、テキスト処理であれば「a」から「z」までの文字などが使われます。

3. 状態遷移関数（δ）

「現在の状態」と「入力記号」の組み合わせから、次に移行すべき「次の状態」を導き出すルールです。

これがマシンの「ロジック」そのものを司る心臓部となります。

4. 初期状態（q0）

マシンが処理を開始する際、最初に位置している状態を指します。

一つのオートマトンに対して、開始地点となる初期状態は必ず一つだけ存在します。

5. 受理状態の集合（F）

入力の読み込みがすべて終了した際、その入力を「正当なもの」として認めるための最終状態の集まりです。

これを「終了状態」と呼ぶこともあり、目的が達成されたことを意味します。

状態遷移図と状態遷移表の役割

有限オートマトンの動作を視覚的に理解するために、「状態遷移図」と「状態遷移表」の2種類が頻繁に活用されます。

状態遷移図による可視化

状態遷移図は、各状態を「円」で描き、入力による遷移を「矢印」でつないだグラフ構造の図です。

一目でどの入力があったときにどの状態へ変化するかが分かるため、設計書や仕様の確認に重宝されます。

矢印の根元に現在の状態があり、矢印に添えられた記号が入力、そして矢印の先が次の状態を示します。

状態遷移表による管理

一方で、プログラムの実装時には「状態遷移表」としてリストアップする手法が一般的です。

縦軸に現在の状態、横軸に入力を配置し、交差するセルに遷移先の状態を記述します。

現在の状態入力：0入力：1
状態 A状態 A状態 B
状態 B状態 A状態 B

このように表形式で整理することで、考慮漏れ（入力に対する遷移の抜け）を防ぐことができます。

決定性有限オートマトン（DFA）の仕組み

決定性有限オートマトン（Deterministic Finite Automaton: DFA）は、動作が完全に一意に決まるモデルです。

「現在の状態」と「特定の入力」が決まれば、次に遷移する先は必ず一つだけに限定されます。

曖昧さが一切存在しないため、コンピュータプログラムとして実装する際に非常に適した形式です。

DFAはメモリを節約しつつ高速に動作するため、キーワード検索アルゴリズムなどで広く利用されています。

また、同じ入力に対しては何度実行しても必ず同じ結果が得られるという再現性の高さも特徴です。

非決定性有限オートマトン（NFA）の仕組み

一方、非決定性有限オートマトン（Nondeterministic Finite Automaton: NFA）は、より柔軟な構造を持っています。

一つの入力に対して、遷移先の候補が複数存在したり、あるいはどの状態へも遷移しなかったりすることが許容されます。

さらに、入力を読み込まなくても勝手に状態を変えられる「イプシロン遷移（ε遷移）」という特殊な動作も可能です。

一見すると不安定に見えますが、複雑な条件分岐を数学的に簡潔に記述できるという大きなメリットがあります。

最終的に一つの正解パスが存在すればその入力を「受理」するため、パターンの探索において非常に強力な理論的ツールとなります。

なお、数学的には「すべてのNFAは、それと等価な動作をするDFAに変換できる」ということが証明されています。

有限オートマトンの具体例：駅の自動改札機

有限オートマトンの概念を理解するために、身近な「自動改札機」を例に考えてみましょう。

このシステムには、大きく分けて「閉鎖中（待機中）」と「開放中（通過可能）」の2つの状態があります。

初期状態は「閉鎖中」であり、このとき人が通ろうとしてもゲートは開きません。

ここで「ICカードのタッチ」という入力が発生すると、状態遷移関数によって状態が「開放中」に切り替わります。

「開放中」の状態で「人が通過する」という入力が入ると、再び状態は「閉鎖中」へと戻ります。

もし「開放中」の状態でもう一度「ICカードのタッチ」が行われた場合、多くの改札機はエラーを出すか、あるいは「開放中」を維持し続けます。

このように、過去にどのような入力があったかによって現在の振る舞いが変わるシステムは、すべて有限オートマトンで説明できます。

有限オートマトンと正規表現の深い関係

エンジニアにとって最も馴染みのある有限オートマトンの応用例は「正規表現」でしょう。

正規表現は、特定の文字列パターンを検索したり置換したりするために使われる強力な構文です。

実は、正規表現で表現できるすべてのパターンは、有限オートマトンによって完全にシミュレート可能です。

正規表現をエンジンが処理する際、内部では正規表現のパターンを一度NFAに変換し、さらに効率的なDFAに変換してから文字列の照合を行っています。

例えば、「ab*c」という正規表現は、「a」が来た後に「b」が0回以上繰り返され、最後に「c」が来る状態遷移を定義していることと同じです。

この理論的な裏付けがあるからこそ、正規表現はあらゆるプログラミング言語で高速かつ正確に動作するのです。

プログラミングにおける実装例

有限オートマトンの考え方をコードに落とし込む際、単純なif文の羅列よりも、状態遷移を意識した構造の方が保守性は高くなります。

以下は、簡単な文字列チェックを行うオートマトンを模したPython風の疑似コードです。

Python
# 簡易的な状態遷移の実装例
class StateMachine:
    def __init__(self):
        # 初期状態を設定
        self.state = "START"

    def transition(self, char):
        # 現在の状態と入力に基づいた分岐
        if self.state == "START":
            if char == "a":
                self.state = "STATE_A"
            else:
                self.state = "ERROR"
        elif self.state == "STATE_A":
            if char == "b":
                self.state = "ACCEPT"
            else:
                self.state = "ERROR"
        
    def is_accepted(self):
        return self.state == "ACCEPT"

# マシンの実行
fsm = StateMachine()
input_string = "ab"

for c in input_string:
    fsm.transition(c)

print(f"Result: {fsm.is_accepted()}")
実行結果
Result: True

このコードは、入力が「ab」である場合のみ「受理」状態になります。

大規模なシステムでは、このようなロジックを「Stateパターン」などのデザインパターンを用いて整理することが推奨されます。

有限オートマトンの限界

非常に便利な有限オートマトンですが、解決できない問題も存在します。

それは、「無限のメモリを必要とする処理」ができないという点です。

例えば、入れ子構造になった括弧の対応チェック（((...))など）は、有限オートマトンだけでは不可能です。

なぜなら、括弧がいくつ開かれたかを数えておくために、無限に近いメモリ（スタック）が必要になる可能性があるからです。

このようなより高度な計算が必要な場合は、「プッシュダウン・オートマトン」や「チューリングマシン」といった、より強力な計算モデルが必要になります。

自分の直面している問題が有限オートマトンで解ける範囲なのか、それともそれ以上の能力を必要とするのかを見極めることが重要です。

まとめ

有限オートマトンは、限られた状態の遷移によってシステムの動作を定義する、シンプルで美しい論理モデルです。

初期状態、入力、遷移ルール、そして受理状態という5つの要素を理解することで、ソフトウェア設計の抽象度を高めることができます。

決定性（DFA）と非決定性（NFA）の違いを把握すれば、正規表現や字句解析の裏側で何が起きているのかが明確に見えてくるはずです。

日々のコーディングにおいても、「現在の状態は何か」「この入力でどう変わるべきか」というオートマトン的な思考を持つことで、バグの少ない堅牢なプログラムを書く手助けとなります。

コンピュータ科学の基礎を支えるこの理論を、ぜひ自身のスキルアップに役立ててみてください。