无需登录 数据私有 本地保存

正则转NFA/DFA可视化 - 编译原理在线演示

15
0
0
0

正则转NFA/DFA可视化

编译原理在线演示 · Thompson构造法 & 子集构造法

(a|b)*abb a(b|c)* (0|1)*01 a*b+ ab?c (ab|cd)* a(a|b)*a

输入正则表达式并点击"生成可视化"

常见问题 & 编译原理知识点

Thompson构造法由Ken Thompson于1968年提出，是一种将正则表达式系统性地转换为NFA（非确定有限自动机）的算法。它采用递归组合的方式，为每种正则运算（连接、选择|、闭包*）定义了标准的NFA构造模板。构造出的NFA具有恰好一个起始状态和一个接受状态，且所有转换边都从起始状态方向指向接受状态方向，这保证了组合的正确性。该算法时间复杂度为O(n)，其中n为正则表达式长度。

子集构造法（Subset Construction）是将NFA转换为等价DFA的标准算法。核心思想是：将NFA的状态集合映射为DFA的单个状态。算法步骤：① 计算NFA起始状态的ε-闭包（通过ε转换可达的所有状态），作为DFA的起始状态；② 对于每个DFA状态（对应一个NFA状态集合）和每个输入符号，计算move操作后再求ε-闭包，得到新的DFA状态；③ 重复直到没有新状态产生。最坏情况下DFA状态数可达2n（n为NFA状态数），但实际中通常远小于此上限。

NFA（非确定有限自动机）：一个状态在相同输入符号下可以有多个后继状态；允许ε转换（不消耗输入符号的状态转移）。
DFA（确定有限自动机）：每个状态在特定输入符号下有且仅有唯一的后继状态；不允许ε转换。
两者在语言识别能力上是等价的（都识别正则语言），但DFA实现更简单（无需回溯），而NFA通常更紧凑（状态数更少）。本工具同时展示两种自动机，便于理解编译原理中的等价转换过程。

本工具支持以下正则运算：
🔤 字面字符：字母a-z A-Z和数字0-9
🔗 连接：ab（隐式，无需显式运算符）
🔄 选择：a|b（匹配a或b）
⭐ Kleene闭包：a*（零次或多次重复）
➕ 正闭包：a+（一次或多次重复，等价于aa*）
❓ 可选：a?（零次或一次，等价于a|ε）
📦 分组：(...)（改变运算优先级）
运算符优先级（从高到低）：闭包*+? > 连接 > 选择|

ε-闭包（Epsilon Closure）是指从一个状态出发，仅通过ε转换（空串转换）就能到达的所有状态的集合（包括自身）。例如，若状态0通过ε转换可到达状态1和状态2，状态1又通过ε转换可到达状态3，则状态0的ε-闭包为{0, 1, 2, 3}。ε-闭包是子集构造法的关键操作，它确保DFA状态正确包含了所有"无需消耗输入即可到达"的NFA状态。

对于DFA：从起始状态开始，依次读入字符串中的每个字符，根据转换表迁移状态。读完所有字符后，若当前状态是接受状态（图中双圈标记），则该字符串被接受。
对于NFA：由于存在非确定性，需要同时追踪所有可能的状态路径。若存在至少一条路径在读完所有字符后到达接受状态，则该字符串被接受。NFA的模拟通常需要维护一个"活跃状态集合"，每读入一个字符就更新该集合（通过move和ε-闭包操作）。
🔧 相关工具