有限オートマトンは、論理的に動作する機械モデルとして利用されています。プログラミング言語の動作モデルや、論理回路の設計等に活用されています。また機械学習においても重要なアルゴリズムである隠れマルコフモデルも、有限オートマトンと類似した構造を持っています。
本記事では、有限オートマトンの基本概念であるDFA（決定性有限オートマトン）とNFA（非決定性有限オートマトン）について解説し、Pythonで実装します。
本記事の内容
- 有限オートマトンの定義と構成要素
- DFA（決定性有限オートマトン）の定義と実装
- NFA（非決定性有限オートマトン）の定義と実装
- NFAからDFAへの変換（部分集合構成法）
有限オートマトンとは
有限オートマトン（Finite Automaton, FA）は、有限個の状態を持ち、入力記号を1つずつ読み取りながら状態を遷移させ、最終的に入力を受理するか拒否するかを判定する計算モデルです。
有限オートマトンは以下の5つの要素 $(Q, \Sigma, \delta, q_0, F)$ で定義されます。
| 記号 | 名称 | 説明 |
|---|---|---|
| $Q$ | 状態の集合 | 有限個の状態 |
| $\Sigma$ | 入力アルファベット | 入力記号の有限集合 |
| $\delta$ | 遷移関数 | 現在の状態と入力から次の状態を決定 |
| $q_0$ | 初期状態 | 計算開始時の状態 ($q_0 \in Q$) |
| $F$ | 受理状態の集合 | 受理を示す状態 ($F \subseteq Q$) |
DFA（決定性有限オートマトン）
DFA（Deterministic Finite Automaton）では、各状態において各入力記号に対する遷移先が一意に決まります。
$$ \delta: Q \times \Sigma \to Q $$
つまり、任意の状態 $q \in Q$ と入力記号 $a \in \Sigma$ に対して、遷移先 $\delta(q, a)$ がちょうど1つ存在します。
DFAの例: “01” を含む文字列の受理
入力アルファベット $\Sigma = \{0, 1\}$ で、部分文字列 “01” を含む文字列を受理するDFAを考えましょう。
- $Q = \{q_0, q_1, q_2\}$
- $q_0$: 初期状態（”01″をまだ見つけていない、直前が1または開始）
- $q_1$: 直前に “0” を読んだ状態
- $q_2$: “01” を見つけた状態（受理状態）
- $F = \{q_2\}$
PythonでDFAを実装
class DFA:
"""決定性有限オートマトン"""
def __init__(self, states, alphabet, transitions, start_state, accept_states):
self.states = states
self.alphabet = alphabet
self.transitions = transitions # {(state, symbol): next_state}
self.start_state = start_state
self.accept_states = accept_states
def run(self, input_string):
"""入力文字列を処理し、受理/拒否を返す"""
current = self.start_state
path = [current]
for symbol in input_string:
if symbol not in self.alphabet:
raise ValueError(f"不正な入力記号: {symbol}")
key = (current, symbol)
if key not in self.transitions:
return False, path
current = self.transitions[key]
path.append(current)
return current in self.accept_states, path
# "01" を含む文字列を受理するDFA
dfa = DFA(
states={'q0', 'q1', 'q2'},
alphabet={'0', '1'},
transitions={
('q0', '0'): 'q1',
('q0', '1'): 'q0',
('q1', '0'): 'q1',
('q1', '1'): 'q2',
('q2', '0'): 'q2',
('q2', '1'): 'q2',
},
start_state='q0',
accept_states={'q2'}
)
# テスト
test_cases = ['01', '001', '110', '1001', '111', '000', '10', '0011']
for s in test_cases:
accepted, path = dfa.run(s)
status = "Accept" if accepted else "Reject"
print(f" '{s}': {status} (path: {' -> '.join(path)})")
NFA（非決定性有限オートマトン）
NFA（Nondeterministic Finite Automaton）では、1つの状態と入力記号に対して、遷移先が複数ある（または0個の場合もある）ことが許されます。
$$ \delta: Q \times \Sigma \to \mathcal{P}(Q) $$
ここで $\mathcal{P}(Q)$ は $Q$ のべき集合（全ての部分集合の集合）です。NFAはいずれかの遷移経路で受理状態に到達すれば、入力を受理します。
PythonでNFAを実装
class NFA:
"""非決定性有限オートマトン"""
def __init__(self, states, alphabet, transitions, start_state, accept_states):
self.states = states
self.alphabet = alphabet
self.transitions = transitions # {(state, symbol): {next_states}}
self.start_state = start_state
self.accept_states = accept_states
def run(self, input_string):
"""入力文字列を処理し、受理/拒否を返す"""
current_states = {self.start_state}
for symbol in input_string:
next_states = set()
for state in current_states:
key = (state, symbol)
if key in self.transitions:
next_states |= self.transitions[key]
current_states = next_states
if not current_states:
return False
return bool(current_states & self.accept_states)
# 末尾が "01" の文字列を受理するNFA
nfa = NFA(
states={'q0', 'q1', 'q2'},
alphabet={'0', '1'},
transitions={
('q0', '0'): {'q0', 'q1'},
('q0', '1'): {'q0'},
('q1', '1'): {'q2'},
},
start_state='q0',
accept_states={'q2'}
)
# テスト
test_cases = ['01', '101', '001', '10', '00', '11', '1101', '0001']
print("NFA: ends with '01'")
for s in test_cases:
accepted = nfa.run(s)
status = "Accept" if accepted else "Reject"
print(f" '{s}': {status}")
NFAからDFAへの変換（部分集合構成法）
計算理論の重要な定理として、任意のNFAに対して等価なDFAが存在します。変換にはNFAの状態の部分集合をDFAの状態とする部分集合構成法（Subset Construction）を用います。
def nfa_to_dfa(nfa):
"""NFAを等価なDFAに変換する（部分集合構成法）"""
# DFAの初期状態はNFAの初期状態の集合
dfa_start = frozenset({nfa.start_state})
dfa_states = set()
dfa_transitions = {}
queue = [dfa_start]
visited = set()
while queue:
current = queue.pop(0)
if current in visited:
continue
visited.add(current)
dfa_states.add(current)
for symbol in nfa.alphabet:
next_states = set()
for state in current:
key = (state, symbol)
if key in nfa.transitions:
next_states |= nfa.transitions[key]
next_frozen = frozenset(next_states)
if next_frozen:
dfa_transitions[(current, symbol)] = next_frozen
if next_frozen not in visited:
queue.append(next_frozen)
# 受理状態: NFAの受理状態を含むDFA状態
dfa_accept = {s for s in dfa_states if s & nfa.accept_states}
return DFA(
states=dfa_states,
alphabet=nfa.alphabet,
transitions=dfa_transitions,
start_state=dfa_start,
accept_states=dfa_accept
)
# NFAからDFAへの変換
converted_dfa = nfa_to_dfa(nfa)
# 変換後のDFAでテスト
print("\nConverted DFA: ends with '01'")
for s in test_cases:
accepted, path = converted_dfa.run(s)
status = "Accept" if accepted else "Reject"
print(f" '{s}': {status}")
状態遷移の可視化
DFAの状態遷移を可視化してみましょう。
import matplotlib.pyplot as plt
import numpy as np
def draw_dfa(states_pos, transitions, start, accepts, title="DFA"):
"""DFAの状態遷移図を描画"""
fig, ax = plt.subplots(figsize=(10, 6))
# 状態の描画
for state, (x, y) in states_pos.items():
color = 'lightgreen' if state in accepts else 'lightskyblue'
circle = plt.Circle((x, y), 0.35, color=color, ec='black', linewidth=2, zorder=5)
ax.add_patch(circle)
if state in accepts:
inner = plt.Circle((x, y), 0.28, fill=False, ec='black', linewidth=1.5, zorder=6)
ax.add_patch(inner)
ax.text(x, y, state, ha='center', va='center', fontsize=12, fontweight='bold', zorder=7)
# 初期状態の矢印
sx, sy = states_pos[start]
ax.annotate('', xy=(sx - 0.35, sy), xytext=(sx - 0.8, sy),
arrowprops=dict(arrowstyle='->', lw=2))
ax.text(sx - 1.0, sy, 'start', ha='center', va='center', fontsize=10)
# 遷移の描画（簡略化）
drawn = {}
for (s1, sym), s2 in transitions.items():
key = (s1, s2)
if key in drawn:
drawn[key] += f', {sym}'
else:
drawn[key] = sym
for (s1, s2), label in drawn.items():
x1, y1 = states_pos[s1]
x2, y2 = states_pos[s2]
if s1 == s2:
# 自己ループ
ax.annotate(label, xy=(x1, y1 + 0.35), fontsize=10, ha='center',
xytext=(x1, y1 + 0.8),
arrowprops=dict(arrowstyle='->', connectionstyle='arc3,rad=-0.5', lw=1.5))
else:
mid_x = (x1 + x2) / 2
mid_y = (y1 + y2) / 2 + 0.2
ax.annotate('', xy=(x2 - 0.35 * (x2-x1)/max(abs(x2-x1)+0.01, 0.01), y2),
xytext=(x1 + 0.35 * (x2-x1)/max(abs(x2-x1)+0.01, 0.01), y1),
arrowprops=dict(arrowstyle='->', lw=1.5))
ax.text(mid_x, mid_y, label, ha='center', va='center', fontsize=10,
bbox=dict(boxstyle='round,pad=0.2', facecolor='white', edgecolor='gray'))
ax.set_xlim(-2, 6)
ax.set_ylim(-1, 3)
ax.set_aspect('equal')
ax.axis('off')
ax.set_title(title, fontsize=14)
plt.tight_layout()
plt.show()
# "01" を含む文字列を受理するDFAの状態遷移図
states_pos = {'q0': (0, 1), 'q1': (2, 1), 'q2': (4, 1)}
draw_dfa(
states_pos=states_pos,
transitions={('q0', '0'): 'q1', ('q0', '1'): 'q0', ('q1', '0'): 'q1', ('q1', '1'): 'q2', ('q2', '0'): 'q2', ('q2', '1'): 'q2'},
start='q0',
accepts={'q2'},
title='DFA: accepts strings containing "01"'
)
まとめ
本記事では、有限オートマトンの基本であるDFAとNFAについて解説しました。
- 有限オートマトンは有限個の状態を持つ計算モデルで、$(Q, \Sigma, \delta, q_0, F)$ で定義される
- DFAは各状態・入力に対して遷移先が一意に決まる決定性モデル
- NFAは遷移先が複数あり得る非決定性モデルで、いずれかの経路で受理すれば入力を受理する
- 部分集合構成法により、任意のNFAを等価なDFAに変換できる
- 有限オートマトンは正規表現、コンパイラの字句解析、隠れマルコフモデルなど多くの分野の基礎となっている