请说明正则、NFA、DFA 的等价性,以及 Thompson 构造、子集构造(NFA→DFA)、DFA 最小化的作用。
正则、有限自动机是词法分析的数学基础,三者等价(描述同一类正则语言):
1. 正则表达式 → NFA(Thompson 构造法):将正则的并 |、连接、闭包 * 自底向上拼成 NFA(含 ε 转移)。
2. NFA → DFA(子集构造法 / Subset Construction):NFA 状态在任意时刻可有多个、含 ε 转移;DFA 每个状态对每个输入符号有且仅有唯一后继、无 ε 转移。子集构造把“NFA 状态集合”映射为“DFA 单个状态”,从而消除不确定性与 ε。
3. DFA 最小化(Hopcroft 等算法):合并等价状态,得到状态数最少的 DFA,提升词法分析效率。
为什么这样做:DFA 执行时无需回溯、每个字符 O(1) 转移,适合高速词法扫描;而正则/NFA 更便于人书写与构造。最终词法分析器(如 Lex 生成)多以最小化 DFA 表驱动运行。
补充:DFA 与正则能力等价,但不能识别需要计数/嵌套的结构(如配对括号),那超出正则语言,需下推自动机(上下文无关文法)。
题目与答案就在本页;收藏、批注和错题重练在应用内