【程序语言与编译】 有限自动机（DFA与NFA）
适合读者：软考中级备考同学
阅读时间：3.5分钟
内容：DFA与NFA的定义、区别、等价转换、例题
1. 什么是有限自动机？
有限自动机（Finite Automaton, FA）是一种识别器，用于判断一个输入字符串是否属于某正规集。它是词法分析的核心工具，也是软考中常考的内容。
有限自动机分为两类：
- 确定型有限自动机（DFA，Deterministic Finite Automaton）
- 非确定型有限自动机（NFA，Nondeterministic Finite Automaton）
二者识别能力等价（任何NFA都可以转换为等价的DFA），但DFA更适合实际实现，NFA更方便人工构造。
2. DFA（确定型有限自动机）
2.1 形式定义
DFA是一个五元组：
M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F)M=(Q,Σ,δ,q0,F)
其中：
- QQQ：有限的状态集合
- Σ\SigmaΣ：有限的输入字母表
- δ\deltaδ：确定的转移函数，δ:Q×Σ→Q\delta: Q \times \Sigma \rightarrow Qδ:Q×Σ→Q（每个状态和输入符号唯一确定下一个状态）
- q0q_0q0：初始状态，q0∈Qq_0 \in Qq0∈Q
- FFF：终止状态集合，F⊆QF \subseteq QF⊆Q
2.2 特点
- 对于当前状态和输入符号，有且只有一个下一状态。
- 状态转移图中，每个结点的出边在相同输入符号上最多一条。
- 实现简单，模拟运行速度快。
2.3 示例
DFA识别所有以01结尾的二进制串：
状态转移表：
| 状态 | 输入0 | 输入1 |
|---|---|---|
| A | A | B |
| B | C | B |
| C | A | B |
初始状态AAA，终止状态CCC。
3. NFA（非确定型有限自动机）
3.1 形式定义
NFA同样是一个五元组：
M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F)M=(Q,Σ,δ,q0,F)
区别在于转移函数δ\deltaδ：Q×(Σ∪{ε})→2QQ \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^QQ×(Σ∪{ε})→2Q（映射到状态集合的子集，而不是单个状态）。
3.2 特点
- 从当前状态读入一个符号后，可能进入多个下一状态（不确定性）。
- 允许ε\varepsilonε转移（不读入任何符号即可跳转）。
- 只要存在一条路径能到达终止状态，NFA就接受该输入串。
3.3 示例
NFA识别以01结尾的串（比DFA更简洁）：
状态图：A→0AA \xrightarrow{0} AA0A，A→1AA \xrightarrow{1} AA1A，A→0BA \xrightarrow{0} BA0B，B→1CB \xrightarrow{1} CB1C（C为终止）。注意从A读0既可以留在A也可以到B，这是非确定性。
4. DFA与NFA对比表
| 对比项 | DFA | NFA |
|---|---|---|
| 下一状态 | 唯一 | 多个或零个 |
| ε\varepsilonε转移 | 不允许 | 允许 |
| 状态数 | 较多 | 较少（通常） |
| 构造难度 | 较难（手动） | 容易（直观） |
| 模拟运行 | 快（无回溯） | 慢（需回溯或子集构造） |
| 识别能力 | 相同 | 相同（等价） |
5. NFA转DFA（子集构造法）
核心思想：将NFA的一个状态子集看作DFA的一个状态。
算法步骤：
- 从初始状态出发，求其ε\varepsilonε闭包（即通过任意步ε\varepsilonε转移能到达的所有状态集合），作为DFA的初始状态。
- 对每个DFA状态（即一个NFA状态集），对于每个输入符号aaa，计算该状态集中所有状态读入aaa后能到达的状态的ε\varepsilonε闭包，得到新的状态子集。若新子集未出现过，则添加到DFA中。
- 重复直到没有新状态产生。
- 若某个DFA状态包含至少一个NFA的终止状态，则该DFA状态为终止状态。
简例（NFA见3.3示例）：
- 初始状态集{A}\{A\}{A}的ε\varepsilonε闭包还是{A}\{A\}{A}。
- 读0：从A出发，0可到A和B →{A,B}\{A,B\}{A,B}闭包（无ε\varepsilonε）→{A,B}\{A,B\}{A,B}。
- 读1：从A出发，1可到A →{A}\{A\}{A}。
- 对新状态{A,B}\{A,B\}{A,B}，读0：从A到A,B，从B无0转移 →{A,B}\{A,B\}{A,B}；读1：从A到A，从B到C →{A,C}\{A,C\}{A,C}。
- {A,C}\{A,C\}{A,C}读0：从A到A,B，C无0 →{A,B}\{A,B\}{A,B}；读1：从A到A，C无1 →{A}\{A\}{A}。
- 最终DFA包含状态{A}\{A\}{A}（初始），{A,B}\{A,B\}{A,B}，{A,C}\{A,C\}{A,C}（终止）。可重命名。
6. 经典例题
题目1：已知NFA的状态转换图如下（文字描述）：状态A初始，A读0可到A和B，A读1到A；B读1到C；C无转移。求该NFA对应的DFA。
（解即为5中的示例，答案为DFA状态集和转移。）
题目2：以下关于DFA和NFA的描述，正确的是（ ）。
A. NFA的识别能力比DFA强
B. DFA不允许ε\varepsilonε转移
C. 每个NFA都可以转换为等价的DFA
D. DFA的状态数一定小于NFA
答案：B和C（A错，能力等价；D错，DFA状态数可能指数增长）
题目3：给定DFA，初始状态0，终止状态2，转移：0读a到1，0读b到0；1读a到2，1读b到1；2读a到2，2读b到2。判断字符串aaba是否被接受。
解：从0开始：a→1；a→2；b→2；a→2。最终在状态2（终止），接受。
答案：接受
7. 记忆口诀
DFA确定唯一路，NFA多路可空跳。
子集构造换等价，识别能力一样高。
8. 给备考同学的一句话
有限自动机是词法分析的数学模型。软考中常见：
- 给定状态图或转移表，判断DFA/NFA类型。
- NFA转DFA（子集构造法，只需理解概念，很少要求完整手工计算复杂例子）。
- 模拟DFA运行，判断字符串是否被接受。
记住：DFA实现简单，NFA构造方便，二者等价。理解子集构造法的思想，考试时遇到相关选择题就能应对。
🔔本专栏日更2篇，点击头像 → 专栏《软考中级高频考点》订阅
#软考中级 #软件设计师 #有限自动机 #DFA #NFA #词法分析