理解计算篇--正则表达式转NFA--理论部分

• 空正则表达式转NFA
• 单字符正则表达式转NFA
• 拼接正则表达式转NFA
• 选择正则表达式转NFA
• 重复正则表达式转NFA

正则表达式转NFA–实战部分

空正则表达式转NFA

转换步骤：

• 构建1个只有1个状态的NFA
• 起始状态也是接受状态
• 没有规则，即规则集为空

单字符正则表达式转NFA

转换步骤：

• 构建1个有2个状态的NFA
• 第一个状态为起始状态，第二个状态为接受状态
• 规则集只有1条规则，当 NFA 处于起始状态，且当前读到的字符等于该正则表达式中的字符时，它会转换到接受状态。

拼接正则表达式转NFA

转换步骤：构建一个新的 NFA

• 新NFA的起始状态为第一个NFA的起始状态
• 新NFA的接受状态集为第二个NFA的接受状态集相同
• 新NFA的规则集包含第一个NFA的所有规则以及第二个NFA的所有规则的并集
• 添加自由移动规则，将第一个 NFA 的每一个旧接受状态连接到第二个 NFA 的旧起始状态

请注意：

• 隐含的改变： 在连接后，第一个 NFA 原来的接受状态在新构建的 NFA 中不再是最终的接受状态
• 无新增状态
• 有新增规则

选择正则表达式转NFA

转换步骤：构建一个新的NFA

• 新 NFA 的起始状态为一个新建的起始状态
• 新 NFA 的接受状态包含两个NFA的接受状态的并集
• 新 NFA 的规则包含两个NFA的规则的并集
• 新增两条额外的自由移动规则：将新的起始状态连接到两个NFA的旧起始状态

请注意：

• 有新增状态，有新增规则

重复正则表达式转NFA

转换步骤：构建一个新的NFA

• 新NFA的起始状态为一个新建的状态，同时也是一个接受状态。
• 新NFA的接受状态包含旧NFA的接受状态
• 新NFA的规则包含旧NFA的规则
• 添加一些额外的自由移动规则，将每个旧NFA的接受状态连接到它的旧起始状态
• 添加一条自由移动规则，将新的起始状态连接到旧起始状态

请注意：

• 有新增状态，有新增规则

示例

(a|b)*a(a|b)