IT 面试题库

正则表达式与有限自动机(NFA/DFA)有什么关系?

中级简答题系统软件工程师编译器工程师正则NFADFA自动机

题目

请说明正则、NFA、DFA 的等价性,以及 Thompson 构造、子集构造(NFA→DFA)、DFA 最小化的作用。

参考答案

内容深度:适中 · 无代码示例 · 来源:外部链接 · 未复核 · 75 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

正则、有限自动机是词法分析的数学基础,三者等价(描述同一类正则语言):

1. 正则表达式 → NFA(Thompson 构造法):将正则的并 |、连接、闭包 * 自底向上拼成 NFA(含 ε 转移)。

2. NFA → DFA(子集构造法 / Subset Construction):NFA 状态在任意时刻可有多个、含 ε 转移;DFA 每个状态对每个输入符号有且仅有唯一后继、无 ε 转移。子集构造把“NFA 状态集合”映射为“DFA 单个状态”,从而消除不确定性与 ε。

3. DFA 最小化(Hopcroft 等算法):合并等价状态,得到状态数最少的 DFA,提升词法分析效率。

为什么这样做:DFA 执行时无需回溯、每个字符 O(1) 转移,适合高速词法扫描;而正则/NFA 更便于人书写与构造。最终词法分析器(如 Lex 生成)多以最小化 DFA 表驱动运行。

补充:DFA 与正则能力等价,但不能识别需要计数/嵌套的结构(如配对括号),那超出正则语言,需下推自动机(上下文无关文法)。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题