正则表达式到有限状态机的转换

Question

你能告诉我把正则表达式转换成有限状态机的算法吗。例如，解析regexp并适当地向fsm添加状态的算法？有什么参考或更深入的想法吗？在

我用Python写这个

谢谢和问候

Answer 1

使用Michael Sipser的Introduction to the Theory of Computation。第1章给出了将正则表达式转换为确定性或非确定性有限状态自动机（DFA或NFA）的详细算法，并证明了它们的等价性（DFA、NFA和正则表达式可以完全匹配相同的字符串类）。在

一般思想是：将正则表达式转换为NFA，这可以非常直接地完成（*是一个循环，|和字符范围是分支点）。然后，将NFA转换为（更大的）DFA，这涉及到为每个可选NFA状态的集创建一个DFA状态。DFA的状态最多与NFA状态集的powerset相同（例如，一个具有3个状态的NFA可以转换为最多2^3=8个状态的DFA），并且可以识别任何目标字符串而不需要回溯。读这本书了解细节。在