正则表达式转 DFA（NFA、子集构造、最小 DFA）
把正则表达式转换为 Thompson NFA、子集构造得到的 DFA 以及最小 DFA，给出转移表，并测试字符串是否被接受。
字母表是表达式中用到的符号的集合：a, b。
最小 DFA 的状态以其合并的 DFA 状态命名；"—" 表示缺失的转移，即输入被拒绝。
| 状态 | ε | a | b |
|---|---|---|---|
| → 0 | {1,2} | — | — |
| 1 | {3,4} | — | — |
| 2 | — | {5} | — |
| 3 | — | {6} | — |
| 4 | — | — | {7} |
| 5 | — | — | {8} |
| 6 | {9} | — | — |
| 7 | {9} | — | — |
| 8 | — | — | {10} |
| 9 | {1,2} | — | — |
| * 10 | — | — | — |
| 状态 | NFA 状态数 | a | b |
|---|---|---|---|
| → A | {0,1,2,3,4} | B | C |
| B | {1,2,3,4,5,6,9} | B | D |
| C | {1,2,3,4,7,9} | B | C |
| D | {1,2,3,4,7,8,9} | B | E |
| * E | {1,2,3,4,7,9,10} | B | C |
| 状态 | a | b |
|---|---|---|
| → AC | B | AC |
| B | B | D |
| D | B | E |
| * E | B | AC |
| 字符串 | 结果 | DFA 路径 |
|---|---|---|
| abb | 接受 | A → B → D → E |
| aabb | 接受 | A → B → B → D → E |
| babb | 接受 | A → C → B → D → E |
| ab | 拒绝 | A → B → D |
| abba | 拒绝 | A → B → D → E → B |
编译原理和自动机课程把正则表达式分三步变成机器：Thompson 构造得到带 ε 转移的 NFA，子集构造把它变成 DFA，最小化则合并行为相同的状态。这个工具对形式化的正则表达式完成这三步，并给出每台机器的转移表（标出起始状态和接受状态），然后把你的测试字符串送入最小 DFA，展示每个字符串所走的路径。
使用方法
- 输入含有 |、*、+、?、括号和 ε（或 eps）的正则表达式。
- 说明 + 表示“一次或多次”，还是像某些教材那样表示“或”。
- 输入要测试的字符串，每行一个（空行测试空串）。
- 查看 NFA、DFA 和最小 DFA 的表格以及接受/拒绝结果。
计算公式
DFA 状态 = NFA 状态集合的 ε 闭包 · move(T, a) = 从 T 出发经 a 可到达的 NFA 状态 · 最小 DFA = 未来行为相同的状态类
Thompson 构造为每个符号建两个状态，每遇到一个 |、*、+ 或 ? 再加两个状态；连接时像龙书一样，把前一部分的末尾与后一部分的开头合并。子集构造按发现顺序把 DFA 状态命名为 A、B、C …。最小化从“接受/非接受”的划分开始，不断细分，直到同一组中的状态对每个符号都转移到相同的组（Moore 算法，结果与 Hopcroft 算法相同）。死状态收集所有缺失的转移，可以显示或隐藏。
示例
对于 (a|b)*abb，Thompson 构造得到 11 个 NFA 状态。子集构造产生 A 到 E 共 5 个 DFA 状态，转移与龙书中的表完全一致，只有 E 是接受状态。A 和 C 的行为相同，所以最小 DFA 有 4 个状态：AC、B、D 和 E。测试字符串中，abb、aabb 和 babb 被接受，ab 和 abba 被拒绝。
常见问题
为什么 DFA 的状态会比 NFA 多？
每个 DFA 状态对应一组 NFA 状态，这样的集合最多有 2ⁿ 个。通常只有少数可达，但有些表达式确实需要指数级数量的状态——工具会在 2,000 个时停止。
这和编程语言中的正则表达式一样吗？
不一样。这里是自动机理论的形式化记法，只有并、连接、星、加号和可选。反向引用、先行断言等功能不是正则的，无法转换成 DFA。
什么是死状态？
对每个符号都转回自己的非接受状态，表示“这个输入永远不会被接受”。表格里通常会省略它；勾选选项即可显示。
资料来源
最后更新:
包含这些输入的页面地址： https://kakao.mobile/zh/tools/regex-to-dfa-tool/
引用此工具
kakaoCalc. (2026, November 8). 正则表达式转 DFA（NFA、子集构造、最小 DFA）. https://kakao.mobile/zh/tools/regex-to-dfa-tool/
“正则表达式转 DFA（NFA、子集构造、最小 DFA）.” kakaoCalc, 8 Nov. 2026, kakao.mobile/zh/tools/regex-to-dfa-tool/.