有限自动机

有限自动机模型

有限自动机（Finite Automaton, FA）由三条核心组件构成：

• 纸带：存储输入符号串
• 读头：从左到右逐字符读取，单向移动
• 状态控制器：有限状态集合，随输入改变

DFA 五元组

确定有限自动机（DFA）定义为 $M=(S,\Sigma ,f,S_0,Z)$：

• $S$：有限状态集
• $\Sigma$：字母表
• $f$：转移函数 $S\times \Sigma \to S$（单值映射）
• $S_0\in S$：唯一初态
• $Z\subseteq S$：终态集

三种表示法：

表示法	形式
形式化定义	$M=(S,\Sigma ,f,S_0,Z)$，给出 $f$ 表格
状态转移图	结点=状态，弧=转移，初态→，终态◎
状态转移矩阵	行=状态，列=输入，单元格=下一状态

识别机制：DFA 从 $S_0$ 出发，按输入串逐字符经 $f$ 转移，若读完输入串时处于 $Z$ 中某状态则接受，否则拒绝。

NFA 五元组

非确定有限自动机（NFA）定义为 $M=(S,\Sigma ,f,S_0,Z)$：

• $S,\Sigma ,S_0,Z$ 含义同 DFA
• $f$：转移函数 $S\times (\Sigma \cup \{\epsilon \})\to 2^S$（多值映射，可含 $\epsilon$）

与 DFA 核心区别：

	DFA	NFA
转移结果	唯一状态	状态集合
$\epsilon$ 转移	不允许	允许
确定性	完全确定	非确定（多分支）

重点 DFA 五元组及三种表示法（形式化/图/矩阵）、NFA 与 DFA 的区别。