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

正则表达式状态机绘制 - NFA/DFA可视化

13
0
0
0

正则表达式状态机绘制

支持 Thompson NFA 构造 & 子集构造法 DFA 转换 · 拖拽节点 · 滚轮缩放

普通状态 接受状态 ε转移
示例：
状态: - 转移: -
拖拽节点调整位置 拖拽空白区域平移画布 滚轮缩放 双击空白重置视图
常见问题与知识点
NFA（非确定性有限自动机）允许从一个状态通过同一符号转移到多个不同状态，也允许 ε（空）转移。而 DFA（确定性有限自动机）对于每个状态和输入符号，最多只有一个确定的转移，且没有 ε 转移。两者表达能力等价。
Thompson 构造法由 Ken Thompson 提出，是一种将正则表达式系统化转换为 NFA 的算法。它使用 ε 转移将小的 NFA 片段组合成更大的 NFA，支持连接、并集（|）和 Kleene 星号（*）等操作。
子集构造法通过计算 NFA 状态的 ε-闭包，将 NFA 的状态集合映射为 DFA 的单个状态。从起始状态的 ε-闭包开始，对每个输入符号计算可达集合，逐步构建出等价的 DFA。最坏情况下 DFA 状态数可达 2ⁿ（n 为 NFA 状态数）。
本工具支持：字面字符（字母a-z、数字0-9）、|（并集/或）、*（零次或多次）、+（一次或多次）、?（零次或一次）、()（分组），以及隐式连接。使用 \ 可转义特殊字符。
🔧 相关工具