软考-软件设计师：程序设计语言-编译过程-词法分析-有限自动机 作者：马育民 • 2025-04-06 13:15 • 阅读：10010 # 概念 有限自动机，也称为有穷自动机，是 **编译原理** 中 **词法分析** 中的概念 是一种识别装置的抽象概念，它能准确地 **识别 正规集**。 ### 理解 如下图，根据箭头线，**从起点走到终点**，将箭头线上的字符，组成字符串，就是可识别的字符串 [](https://www.malaoshi.top/upload/0/0/1GWtbSo0Dqe.png) **提示：** 大圈套小圈，表示 **终点** 上图中，`S`是起点，`F`是终点，**S->F可识别的串：** - S-A-F : `10` - S-A-C-F : `11(0|1)` - S-B-F : `01` - S-B-C-F : `00(0|1)` ### 考点 能够从 **起点** 走到 **终点**，识别的字符串 ### 分类 - 确定的有限自动机(DFA)：一个状态面对一个输入符号的时候，所转换到的是 **一个唯一** 确定的状态 - 不确定的有限自动机(NFA)：当一个状态面对一个输入符号的时候，它所转换到的可能不只一个状态，可以是 **一个状态集合** # 题 对高级语言源程序进行编译的过程中，有穷自动机（NFA或DFA）是进行（）的适当工具。 A.词法分析 B.语法分析 C.语义分析 D.出错处理 ### 答 A # 题 下图所示为一个不确定有限自动机(NFA)的状态转换图。该NFA可识别字符串 （） [](https://www.malaoshi.top/upload/0/0/1GWtbeRRco9.png) A、0110 B、0101 C、1100 D、1010 ### 分析 **提示：**对于 `ε` 的边表示 **零代价的转换**，可以在没有任何输入操作的情况下直接滑动到下一个，也就是 上一个 与下一个 是等价的 从上图可知，起点是 `0`，所以 C、D 都是错的 A是正确的，路径如下： [](https://www.malaoshi.top/upload/0/0/1GWtcDhyukG.png) # 题 下图所示有限自动机（DFA）是（）。 [](https://www.malaoshi.top/upload/0/0/1GWtcbJ0Y9f.png) A、确定的有限自动机，它能识别以bab结尾的 B、确定的有限自动机，他不能识别以bab结尾的 C、非确定的有限自动机，他能识别以bab结尾的 D、非确定的有限自动机，他不能识别以bab结尾的 ### 分析 起点可以是多个 `a` 或 多个 `b` ，所以是不确定有限自动机 根据下图红框部分可知：可以是 `aa`、`ab`、`ba`、`bb` [](https://www.malaoshi.top/upload/0/0/1GWtcgCoBRv.png) ### 答案 D 参考： https://blog.csdn.net/guangod/article/details/101672919 原文出处：http://malaoshi.top/show_1GWtchS2Key.html