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

Question

你会有一个提示算法将任何正则表达式转换为有限状态机.例如,解析正则表达式并将状态适当地添加到fsm的算法？任何参考或更深层的想法？

我用Python写这个

感谢致敬

Answer 1

使用Michael Sipser的计算理论导论.第1章给出了将正则表达式转换为确定性或非确定性有限状态自动机(DFA或NFA)的详细算法,在证明它们的等价性的背景下(DFA,NFA和正则表达式可以完全匹配相同的类)字符串).

一般的想法是:将正则表达式转换为NFA,这可以非常简单地完成(*是循环,|字符范围是分支点).然后,您可以转换NFA成(更大)DFA,其中包括对每个创建一个DFA状态组的替代NFA状态.DFA最多具有与NFA状态集的幂集一样多的状态(例如,具有3个状态的NFA可以转换为具有最多2 ^ 3 = 8个状态的DFA),并且可以识别任何目标字符串而无需回溯.阅读本书了解详情.