文章目錄

• 一、正則表達式轉為非確定性有限自動機 NFA 要點
• 二、正則表達式轉為非確定性有限自動機 NFA 示例 1
• 三、正則表達式轉為非確定性有限自動機 NFA 示例 2
• 四、正則表達式轉為非確定性有限自動機 NFA 示例 3

一、正則表達式轉為非確定性有限自動機 NFA 要點

---

正則表達式轉為非確定性有限自動機 NFA 流程 :

① 原子自動機 : 首先要構造 原子自動機 , 從 非接受狀態 指向 接受狀態 ;

② 基本拼裝 : 將原子自動機進行 基本的拼裝 , 并運算 , 交運算 ;

③ 復雜拼裝 : 將 基本拼裝的自動機 進行 進一步拼裝 ;

拼裝原則 : 使用 $\epsilon$ 箭頭 進行拼裝 ;

① 串聯 : 前者的接受狀態 使用 $\epsilon$ 箭頭 指向 后者的開始狀態 , 前者接受狀態取消 ; 如果有兩個接受狀態 , 那么就需要引出兩個箭頭

② 并聯 : 在二者之前 , 重新添加一個非接受狀態的開始狀態 , 使用兩個 $\epsilon$ 箭頭 分別指向二者的開始狀態 ;

③ 星運算 : 重新添加一個接受狀態的開始狀態 , 使用 $\epsilon$ 箭頭從 接受狀態 指向 開始狀態 ; 注意所有的接受狀態 , 都要使用 $\epsilon$ 箭頭指向開始狀態 ;

二、正則表達式轉為非確定性有限自動機 NFA 示例 1

---

將正則表達式 $(0\cup 1{)}^{?}000(0\cup 1{)}^{?}$ 轉為 NFA ;

構造原子自動機 : 注意從 非接受狀態 $\to$ 接受狀態 ;

$(0\cup 1)$ 并聯拼裝 : 在二者前面添加 非接受狀態 起始狀態 ;

$(0\cup 1{)}^{?}$ 星運算 : 使 接受狀態 $\to$ 起始狀態 , 并添加一個 接受狀態 起始狀態 , 指向原來的起始狀態 ;

$000$ 串聯 : 前者的接受狀態 必須轉為 非接受狀態 , 前者的接受狀態 必須轉為 非接受狀態 , 后者的狀態是不變的 ;

總拼裝 :

串聯注意事項 : $(0\cup 1{)}^{?}$ 有 $3$ 個接受狀態 , 需要引出 $3$ 個 $\epsilon$ 箭頭 指向 $000$ 代表的自動機 的 開始狀態 ;

串聯時的狀態改變 : 使用 $\epsilon$ 箭頭 連接 前者的接受狀態 $\to$ 后者的起始狀態;

串聯時 前者的接受狀態 必須轉為 非接受狀態 ,

后者的狀態是不變的 , 如果是接受狀態 , 那么就保持接受狀態不變 , 同理如果是非接受狀態 , 那么保持非接受狀態不變 ;

化簡后結果 :

三、正則表達式轉為非確定性有限自動機 NFA 示例 2

---

將正則表達式 $(((00{)}^{?}(11))\cup 01{)}^{?}$ 轉為 NFA ;

構造原子自動機 : 注意從 非接受狀態 $\to$ 接受狀態 ;

$00$ 串聯 : 前者的接受狀態 必須轉為 非接受狀態 , 前者的接受狀態 必須轉為 非接受狀態 , 后者的狀態是不變的 ;

$(00{)}^{?}$星運算 : 使 接受狀態 $\to$ 起始狀態 , 并添加一個 接受狀態 起始狀態 , 指向原來的起始狀態 ;

$11$ 串聯 : 前者的接受狀態 必須轉為 非接受狀態 , 前者的接受狀態 必須轉為 非接受狀態 , 后者的狀態是不變的 ;

$((00{)}^{?}(11))$ 串聯 : 前者的接受狀態 必須轉為 非接受狀態 , 前者的接受狀態 必須轉為 非接受狀態 , 后者的狀態是不變的 ;

$((00{)}^{?}(11))\cup 01$ 并聯 : 在二者前面添加 非接受狀態 起始狀態 ;

$(((00{)}^{?}(11))\cup 01{)}^{?}$ 星運算 : 使 接受狀態 $\to$ 起始狀態 , 并添加一個 接受狀態 起始狀態 , 指向原來的起始狀態 ;

化簡后結果 :

四、正則表達式轉為非確定性有限自動機 NFA 示例 3

---

將正則表達式 ${?}^{?}$ 轉為 NFA ;

${?}^{?}$ $=\{\epsilon \}$

構造原子自動機 : 注意從 非接受狀態 $\to$ 接受狀態 ;

總結

以上是生活随笔為你收集整理的【计算理论】计算理论总结 ( 正则表达式转为非确定性有限自动机 NFA | 示例 ) ★★的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。