从正则表达式到有穷自动机

思路: 从正则表达式转换到 NFA, 再转换为 DFA

flowchart LR
RE -.-> NFA -.-> DFA 
RE --> DFA

正则表达式到 NFA

• $\epsilon$对应的NFA
• 字母表$\Sigma$中符号$a$对应的 NFA
• $r=r_1r_2$对应的 NFA
• $r=r_1|r_2$对应的 NFA
• $r=(r_1)^*$对应的 NFA

NFA 到 DFA

1. 根据 NFA 画出转换表, 其中每一行代表状态, 每一列代表输入
2. 构建 DFA, 其开始节点与 NFA 相同
3. 根据转换表补出 DFA 剩余部分

例 1

例 2