將正則表達式轉換爲有限狀態機

Question

您是否有提示將任何正則表達式轉換爲有限狀態機的算法。例如，一個算法解析一個正則表達式並適當添加狀態到fsm？任何參考或更深的想法？

我與Python書面方式這

感謝和問候

Answer 1

使用邁克爾·西蓬瑟的Introduction to the Theory of Computation。第1章給出了在證明它們的等價性（DFA，NFA和正則表達式可以完全匹配相同的類）的情況下將正則表達式轉換爲確定性或非確定性有限狀態自動機（DFA或NFA）的詳細算法的字符串）。

總體思路是：將正則表達式轉換爲NFA，這可以非常直接地完成（*是一個循環，|，字符範圍是分支點）。然後，您將NFA轉換爲（更大的）DFA，其中包括爲替代NFA狀態的每個集合創建一個DFA狀態。 DFA的狀態與NFA狀態集合的狀態一樣多（例如，具有3個狀態的NFA可以被轉換爲最多2^3 = 8個狀態的DFA），並且可以識別任何目標字符串而不回溯。詳細閱讀本書。