17.2.5 有限自动机

有限自动机是识别正规集的机器模型。它不理解“含义”，只根据当前状态和下一个输入符号决定下一步走到哪里。词法分析器识别关键字、标识符、数字常量时，底层思想就接近这种状态机。

自动机的五个组成

组成	含义
状态集合	自动机可能处于的有限个状态
输入字母表	可读入的符号集合
状态转换函数	当前状态读入某符号后转到哪个状态
初态	识别开始的状态
终态/接受态	输入读完时停在此类状态则接受

图中常用一个没有来源的箭头指向初态，用双圈表示终态。

怎样判断一个串是否被识别

核心规则只有一句：从初态出发，按输入串从左到右逐字符走边；所有字符读完后，如果停在终态，则该串被接受。

stateDiagram-v2
  [*] --> q0
  q0 --> q0: 0
  q0 --> q1: 1
  q1 --> q0: 0

上图中 0 可被接受，10 也可回到 q0 被接受；如果终态是 q0，那么 01 读完停在 q1，不接受。

DFA 与 NFA

类型	特点	判断方法
DFA	每个状态读入每个符号时下一状态唯一	一条路径走到底
NFA	可能存在多个下一状态或空串 $\epsilon$ 转换	只要存在一条路径到终态就接受

NFA 中的空串转换表示“不消耗输入符号也可以换状态”。做题时不要漏掉 $\epsilon$ 可达状态，否则很容易错判。

自动机与正规式互判

自动机和正规式等价，意味着两件事同时成立：

1. 自动机能识别的每个串，正规式都能表示。
2. 正规式能表示的每个串，自动机都能识别。

所以选择题中非常适合用反例排除。课程里给出的思路是：如果某选项能表示 01，但自动机走 01 后不能到达终态，那么该选项一定不等价；如果自动机能识别 0101000，但某选项表示不了这个串，也可以排除。

从状态图读规律

图上结构	语言规律
终态上有 0 自环	可以连续读任意多个 0
从终态读 1 到非终态，再读 0 回终态	10 可作为一个块出现
一个状态无某符号出边	读到该符号的路径失败
存在 $\epsilon$ 边	可不消耗输入进入更多候选状态

例如“若干个 0 或 10 块任意拼接”可写成 (0|10)*。这个表达式不仅能表示 0000，也能表示 0101000，因为它可以拆成 0 10 10 0 0。

小练习

题：在 NFA 中，一个输入串有多条可走路径，其中一条最终到达终态，另一条失败，该串是否被接受？

答：接受。NFA 的接受条件是“存在至少一条成功路径”。

自查

1. 自动机接受字符串的判定条件是什么？
2. NFA 的 $\epsilon$ 转换为什么会影响识别路径？
3. 判断自动机和正规式等价时，应该找哪两类反例？