有限自动机入门
学习目标
通过本集的学习，你将能够：
- 理解什么是自动机
- 掌握确定有限自动机(DFA)
- 学会DFA的图形表示
- 理解DFA的形式化定义
1. 什么是自动机？
自动机是一个抽象的数学模型，它可以处于有限个状态中的某一个状态，并根据输入进行状态转换。
1.1 生活中的自动机类比
自动售货机就是一个自动机：
状态：
- 等待投币
- 已投币
- 选择商品
- 出货中
输入：
- 投币
- 选择商品
- 退款
状态转换：
等待投币 ──投币──→ 已投币
已投币 ──选择──→ 出货中
出货中 ──完成──→ 等待投币1.2 自动机的基本概念
自动机的组成：
1. 有限的状态集合
2. 输入字母表
3. 状态转换函数
4. 开始状态
5. 接受状态集合2. 确定有限自动机 (DFA)
2.1 DFA 的定义
确定有限自动机（Deterministic Finite Automaton，简称 DFA）是一种最简单的自动机。
DFA 的特点：
- 对于每个状态和每个输入符号，只有一个下一状态
- 没有 ε 转移（不需要输入就能转移）
- 确定性：不存在歧义2.2 DFA 的形式化定义
DFA = (Q, Σ, δ, q0, F)
其中：
Q: 有限状态集合
Σ: 输入字母表
δ: 状态转换函数 δ: Q × Σ → Q
q0: 开始状态，q0 ∈ Q
F: 接受状态集合，F ⊆ Q3. DFA 的图形表示
3.1 状态图
我们用状态图来直观地表示 DFA。
图形表示约定：
- 圆圈表示状态
- 双圆圈表示接受状态
- 箭头表示状态转换
- 箭头上的标签表示输入符号
- 没有起点的箭头指向开始状态3.2 示例：识别以 "ab" 结尾的字符串
目标：识别所有以 "ab" 结尾的字符串
DFA 的状态图：
┌───┐
│ a │
└─┬─┘
│ a
▼
┌───┐ ┌───┐ ┌───┐
│ q0│─→│ q1│─→│ q2│
└───┘ └───┘ └───┘
↑│ │b │↑
││ │ ││
│└───┐ └──────┘│
│ │ │
│ b │ a,b │
└────┴──────────┘
状态说明：
q0: 开始状态，还没看到 'a'
q1: 刚看到 'a'
q2: 刚看到 'b' 跟随在 'a' 后面（接受状态）3.3 另一个示例：识别包含 "aa" 的字符串
目标：识别所有包含子串 "aa" 的字符串
状态图：
┌───┐
│ a │
└─┬─┘
│
▼
┌───┐ ┌───┐ ┌───┐
│ q0│─→│ q1│─→│ q2│
└───┘ └───┘ └───┘
│ │ │↑
│ b │ b ││ a,b
└──────┴──────┘┘
状态说明：
q0: 没看到 'a'
q1: 看到一个 'a'
q2: 看到两个 'a'（接受状态）4. DFA 的状态转换表
4.1 转换表
我们也可以用表格来表示状态转换函数。
以 "ab" 结尾的 DFA 转换表：
状态\输入 | a | b
----------|-------|-------
q0 | q1 | q0
q1 | q1 | q2
q2 | q1 | q0
接受状态：{q2}4.2 使用转换表
输入字符串："aab"
处理过程：
当前状态: q0
输入 'a' → q1
输入 'a' → q1
输入 'b' → q2 (接受状态！)
结果：接受5. DFA 的工作原理
5.1 处理字符串的步骤
DFA 处理字符串的过程：
1. 从开始状态开始
2. 对于字符串中的每个字符：
a. 根据当前状态和当前字符查找转换
b. 移动到下一状态
3. 处理完所有字符后：
a. 如果在接受状态 → 接受
b. 否则 → 拒绝5.2 示例运行
DFA：识别以 "ab" 结尾的字符串
示例1：输入 "ab"
步骤：
q0 ─a→ q1 ─b→ q2 (接受状态)
结果：接受 ✓
示例2：输入 "aab"
步骤：
q0 ─a→ q1 ─a→ q1 ─b→ q2 (接受状态)
结果：接受 ✓
示例3：输入 "abc"
步骤：
q0 ─a→ q1 ─b→ q2 ─c→ ??? (没有 'c' 的转换，拒绝)
结果：拒绝 ✗
示例4：输入 "ba"
步骤：
q0 ─b→ q0 ─a→ q1 (不是接受状态)
结果：拒绝 ✗6. 实用案例
6.1 案例1：识别二进制偶数
目标：识别二进制表示的偶数（以0结尾）
DFA 设计：
状态：
- q0: 开始状态
- q1: 最后看到0（接受状态）
- q2: 最后看到1
状态图：
0
┌───┐ ┌───┐
│ q1│←│ q0│
└───┘ └─┬─┘
↑│ │
││ 1 │
│└────┘
│
│ 1 0
└────→┐
│
┌───┐ ┌───┐
│ q2│←─│ │
└───┘ └───┘6.2 案例2：用 Python 实现 DFA
class DFA:
def __init__(self, states, alphabet, transitions, start_state, accept_states):
self.states = states
self.alphabet = alphabet
self.transitions = transitions
self.start_state = start_state
self.accept_states = accept_states
def accepts(self, string):
current_state = self.start_state
for char in string:
if char not in self.alphabet:
return False
current_state = self.transitions[current_state][char]
return current_state in self.accept_states
# 创建识别以 "ab" 结尾的 DFA
states = {'q0', 'q1', 'q2'}
alphabet = {'a', 'b'}
transitions = {
'q0': {'a': 'q1', 'b': 'q0'},
'q1': {'a': 'q1', 'b': 'q2'},
'q2': {'a': 'q1', 'b': 'q0'}
}
start_state = 'q0'
accept_states = {'q2'}
dfa = DFA(states, alphabet, transitions, start_state, accept_states)
# 测试
print(dfa.accepts("ab")) # True
print(dfa.accepts("aab")) # True
print(dfa.accepts("ba")) # False
print(dfa.accepts("abc")) # False7. 自测问题
- 什么是有限自动机？
- DFA 中 "确定" 是什么意思？
- DFA 由哪几个部分组成？
- 如何用状态图表示 DFA？
- DFA 如何处理一个字符串？
8. 下集预告
下一集我们将学习不确定有限自动机 (NFA)！
参考资料
- 《编译原理》（龙书）
- 《自动机理论、语言和计算导论》