将正则表达式转换为有限状态机

将正则表达式转换为有限状态机

使用Michael
Sipser的计算理论导论。第1章详细介绍了在证明等价性的情况下将正则表达式转换为确定性或非确定性有限状态自动机（DFA或NFA）的算法（DFA，NFA和正则表达式可以完全匹配相同的类字符串）。

总体思路是：将正则表达式转换为NFA，可以很直接地完成 *** 作（

*

是一个循环，

|

而字符范围是分支点）。然后，您可以转换NFA成（更大）DFA，其中包括对每个创建一个DFA状态
组 的替代NFA状态。DFA最多具有与NFA状态集的幂集一样多的状态（例如，具有3个状态的NFA可以转换为具有最多2 ^ 3 =
8个状态的DFA），并且可以识别任何目标字符串而无需回溯。阅读本书以获取详细信息。