- 空正則表達式轉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)
)
