文章目錄

• 一、推廣型的非確定性有限自動機 ( GNFA ) 引入
• 二、推廣型的非確定性有限自動機 ( GNFA ) 刪除狀態
• 三、確定性有限自動機 ( DFA ) 轉為 正則表達式
• 四、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 1 ) 添加開始狀態 $S$ 和結束狀態 $T$
• 五、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 2 ) 刪除 狀態 $2$ 刪除方法
• 六、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 2 ) 刪除 狀態 $2$ 信息梳理
• 七、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 2 ) 刪除 狀態 $2$ : $1$ -> $2$ -> $3$ 生成信息 $1$ -> $3$
• 八、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 2 ) 刪除 狀態 $2$ : $3$ -> $2$ -> $3$ 生成信息 $3$ -> $3$
• 九、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 2 ) 刪除 狀態 $2$ 階段性結果
• 十、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 3 ) 刪除 狀態 $1$ 信息梳理
• 十一、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 3 ) 刪除 狀態 $1$ : $3$ -> $1$ -> $3$ 生成信息 $3$ -> $3$
• 十二、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 3 ) 刪除 狀態 $1$ : $S$ -> $1$ -> $3$ 生成信息 $S$ -> $3$
• 十三、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 2 ) 刪除 狀態 $2,1$ 階段性結果
• 十四、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 4 ) 刪除 狀態 $3$ 信息梳理
• 十五、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 4 ) 刪除 狀態 $3$ : $S$ -> $3$ -> $T$ 生成信息 $S$ -> $T$
• 十六、確定性有限自動機 ( DFA ) 轉為 正則表達式 總結

一、推廣型的非確定性有限自動機 ( GNFA ) 引入

---

1 . 給定一個自動機 , 必有一個正則表達式可以表示其所識別的語言 ;

2 . 引入 推廣型的非確定性有限自動機 ( GNFA ) : 首先要構造一個推廣的一般型的非確定性有限自動機 , 每次消除一個狀態 , 最后只剩下兩個狀態 , 此時箭頭上的正則表達式就是最終的正則表達式 ;

上述自動機是一個 推廣型的非確定性有限自動機 ( GNFA ) , 箭頭上 不是單個字符 或 空字符 , 而是 正則表達式 ;

3 . 推廣型的非確定性有限自動機 ( GNFA ) 中的推廣的體現 :

① 非確定性有限自動機 ( NFA ) : 箭頭上 只能出現 字符 , 空字符串 , $2$ 種輸入 , 不能出現其它輸入內容 ;

② 推廣型的非確定性有限自動機 ( GNFA ) : 箭頭上 可以出現 字符 , 空字符串 , 空集 , 正則表達式 , $4$ 種輸入 ;

4 . 推廣型的非確定性有限自動機 ( GNFA ) 與 非確定性有限自動機 ( NFA ) 是等價的 ;

二、推廣型的非確定性有限自動機 ( GNFA ) 刪除狀態

---

給定一個 推廣型的非確定性有限自動機 ( GNFA ) , 找到一個正則表達式 , 代表給定自動機的語言 ;

1 . 需求描述 : 上述自動機中 , $R_1,R_2,R_3,R_4$ 都是正則表達式 ;

刪除 $q_0$ 狀態 : 目前希望能刪除 自動機中的 $q_0$ 狀態 , 刪除 $q_0$ 之后 , 會省略一部分語言 , 這里 省略了 $R_1,R_2,R_3$ ;

語言要求 : 將 $q_0$ 狀態刪除后 , 不影響整個自動機所接受的語言 , 那么需要將省略的部分語言 , 補充到 $R_4$ 中 ;

2 . $R_1,R_2,R_3$ 關系分析 :

① $R_2$ 星運算 : $R_2$ 是一個循環 , $q_0$ 接受 $R_2$ 后 , 仍然保持 $q_0$ 狀態 , 這里的該循環的正則表達式表示為 $(R_2{)}^{?}$ ;

② $R_1$ 與 $(R_2{)}^{?}$ 串聯運算 : $R_1$ 與 $(R_2{)}^{?}$ 是串聯關系 , 表示為 $R_1(R_2{)}^{?}$

③ 與 $R_3$ 的串聯運算 : $R_1(R_2{)}^{?}$ 與 $R_3$ 是串聯關系 , 表示為 $R_1(R_2{)}^{?}{R}_3$ ;

3 . 并運算 : $R_1(R_2{)}^{?}{R}_3$ 與 $R_4$ 是并集關系 , 都是 $q_i$ 到 $q_j$ 的輸入的正則表達式 ;

4 . 兩個正則表達式并運算表示為 : $(R_1(R_2{)}^{?}{R}_3)\cup R_4$

三、確定性有限自動機 ( DFA ) 轉為 正則表達式

---

上圖中的自動機是一個 $3$ 個狀態的 確定性有限自動機 ( DFA ) ;

將上述 確定性有限自動機 ( DFA ) 轉為正則表達式 ;

四、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 1 ) 添加開始狀態 $S$ 和結束狀態 $T$

---

1 . 添加開始和結束狀態 :

① 添加開始狀態 : 添加新的開始狀態 $S$ , 使用 $\epsilon$ 箭頭指向當前 確定性有限自動機 ( DFA ) 的 開始狀態 ;

② 添加結束狀態 : 再次添加一個 接受狀態 , 從 確定性有限自動機 ( DFA ) 的接受狀態 指向該新的結束狀態 , 該新添加的結束狀態 是 接受狀態 ;

2 . 確定性有限自動機 ( DFA ) 轉為 正則表達式 思想 : 逐步刪除 $1,2,3$ 狀態 , 每次刪除一個狀態 , 生成新的正則表達式 , 最后就剩下 開始狀態 $S$ , 和結束狀態 $T$ , 最后剩下的就是 $S$ 到 $T$ 狀態的正則表達式 , 也是自動機的正則表達式 ;

五、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 2 ) 刪除 狀態 $2$ 刪除方法

---

1 . 刪除 $2$ 狀態 :

① 信息抽取轉移 : 找到 與 $2$ 狀態 所有的相關的信息 , 添加到其它的箭頭上 , 如果沒有創建一個新的箭頭 ;

② $2$ 狀態的輸入和輸出 : 哪些狀態 有箭頭 輸入到 $2$ 狀態 , $2$ 狀態 有哪些箭頭 輸出到了其它狀態 ;

③ 信息轉移 : 將每個輸入 和 每個輸出的信息全部轉移 , 一條信息也不能遺漏 ;

④ $2$ 狀態的輸入輸出統計 : 有 $3$ 條輸入 , $2$ 條輸出 ; 其中有 一條輸入輸出是從 $2$ 狀態輸出指向 它自己 , 共有 $4$ 個箭頭信
息 ; 外部輸入有 2 條 , 外部輸出 有 $1$ 條 , 需要生成的箭頭信息個數是 $外部輸入條數\times 外部輸出條數$ ;

2 . $2$ 狀態的循環 ( $1$ 輸入 $1$ 輸出 ) : $2$ 狀態下讀取 $b$ , 仍然回到 $2$ 狀態 ; 這 $1$ 個輸入 , $1$ 個輸出 , 是從 $2$ 狀態輸出到 $2$ 狀態 , 這是一個 星計算 ; 使用 $b^{?}$ 表示 ;

六、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 2 ) 刪除 狀態 $2$ 信息梳理

---

狀態 $2$ 信息梳理如下 ;

1 . $2$ 狀態信息輸入 :

$S$ 狀態 讀取 $\epsilon$ 跳轉到 $1$ 狀態 ;

$3$ 狀態 讀取 $a$ 跳轉到 $1$ 狀態 ;

2 . $2$ 狀態信息輸出 :

$1$ 狀態讀取 $(a{b}^{?}a)\cup b$ 正則表達式 跳轉到 $3$ 狀態 ;

3 . 箭頭信息生成個數 : 外部輸入有 2 條 , 外部輸出 有 $1$ 條 , 需要生成的箭頭信息條數 :

$$外部輸入條數\times 外部輸出條數=2\times 1=2$$

七、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 2 ) 刪除 狀態 $2$ : $1$ -> $2$ -> $3$ 生成信息 $1$ -> $3$

---

1 . $1$ -> $2$ -> $3$ 狀態跳轉 :

$1$ 狀態讀取 $a$ 跳轉到 $2$ 狀態 : 這里是狀態 $2$ 的一條輸入 , 使用 $a$ 表示 ;

$2$ 狀態讀取 $b$ 跳轉到 $2$ 狀態 : 這是無限的星計算 , 使用 $b^{?}$ 表示 ;

$2$ 狀態讀取 $a$ 跳轉到 $3$ 狀態 : 這里是狀態 $2$ 的一條輸出 , 使用 $a$ 表示 ;

2 . $3$ 個正則表達式是串聯關系 ;

中間經歷的過程是 $1$ 狀態輸入 $a$ 跳轉到 $2$ 狀態 , $2$ 本身可以有無限個星計算 , $2$ 狀態輸入 $a$ 跳轉到 $3$ 狀態 ;

使用正則表達式表示為 $a{b}^{?}a$ ;

4 . 生成箭頭信息 :

$1$ 狀態下 , 讀取 $a{b}^{?}a$ 正則表達式 , 可以跳轉到 $3$ 狀態 ;

將 $a{b}^{?}a$ 正則表達式 與 $1$ 到 $3$ 跳轉箭頭上的 $b$ 進行并計算 , 得到

$$(a{b}^{?}a)\cup b$$

這是 $1$ 跳轉到 $3$ 的正則表達式 ;

八、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 2 ) 刪除 狀態 $2$ : $3$ -> $2$ -> $3$ 生成信息 $3$ -> $3$

---

1 . $3$ -> $2$ -> $3$ 狀態跳轉 :

$3$ 狀態讀取 $b$ 跳轉到 $2$ 狀態 : 這里是狀態 $2$ 的一條輸入 , 使用 $b$ 表示 ;

$2$ 狀態讀取 $b$ 跳轉到 $2$ 狀態 : 這是無限的星計算 , 使用 $b^{?}$ 表示 ;

$2$ 狀態讀取 $a$ 跳轉到 $3$ 狀態 : 這里是狀態 $2$ 的一條輸出 , 使用 $a$ 表示 ;

2 . $3$ 個正則表達式是串聯關系 ;

中間經歷的過程是 $3$ 狀態輸入 $b$ 跳轉到 $2$ 狀態 , $2$ 本身可以有無限個星計算 , $2$ 狀態輸入 $a$ 跳轉到 $3$ 狀態 ;

三者串聯關系 , 使用正則表達式表示為 $b{b}^{?}a$ ;

即 $3$ 狀態下 , 讀取 $b{b}^{?}a$ 正則表達式 , 可以跳轉到 $3$ 狀態 ;

3 . 生成箭頭信息 :

給 $3$ 狀態添加一個箭頭指向它自身 , 箭頭的接收的正則表達式是

$$b{b}^{?}a$$

這是 $1$ 跳轉到 $3$ 的正則表達式 ; 表示 $3$ 狀態下接收 $b{b}^{?}a$ 正則表達式 , 仍然跳轉到 $3$ 狀態 ;

九、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 2 ) 刪除 狀態 $2$ 階段性結果

---

刪除 $2$ 狀態結果 :

十、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 3 ) 刪除 狀態 $1$ 信息梳理

---

狀態 $1$ 信息梳理如下 ;

1 . $1$ 狀態信息輸入 :

$S$ 狀態 讀取 $\epsilon$ 跳轉到 $1$ 狀態 ;

$3$ 狀態 讀取 $a$ 跳轉到 $1$ 狀態 ;

2 . $1$ 狀態信息輸出 :

$1$ 狀態讀取 $(a{b}^{?}a)\cup b$ 正則表達式 跳轉到 $3$ 狀態 ;

3 . 箭頭信息生成個數 : 外部輸入有 2 條 , 外部輸出 有 $1$ 條 , 需要生成的箭頭信息條數 :

$$外部輸入條數\times 外部輸出條數=2\times 1=2$$

十一、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 3 ) 刪除 狀態 $1$ : $3$ -> $1$ -> $3$ 生成信息 $3$ -> $3$

---

1 . $3$ -> $1$ -> $3$ 狀態跳轉 :

$3$ 狀態 讀取 $a$ 跳轉到 $1$ 狀態 , 正則表達式 表示為 $a$ ;

$1$ 狀態 讀取 $(a{b}^{?}a)\cup b$ 正則表達式 跳轉到 $3$ , 正則表達式 表示為 $(a{b}^{?}a)\cup b$ ;

2 . 正則表達式 : 上述兩個正則表達式是串聯關系 , 正則表達式表示為 $a((a{b}^{?}a)\cup b)$

3 . 生成新的箭頭信息 :

新增加的 $3$ 狀態下讀取 $a((a{b}^{?}a)\cup b)$ 跳轉到 $3$ ;

與原來的 $3$ 讀取 $b{b}^{?}a$ 跳轉到 $3$ 是并聯關系 ,

最終的 $3$ 讀取一個正則表達手 跳轉到 $3$ 狀態 , 的正則表達式為

$$(a((a{b}^{?}a)\cup b))\cup (b{b}^{?}a)$$

十二、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 3 ) 刪除 狀態 $1$ : $S$ -> $1$ -> $3$ 生成信息 $S$ -> $3$

---

1 . $S$ -> $1$ -> $3$ 狀態跳轉 :

$S$ 狀態 讀取 $\epsilon$ 跳轉到 $1$ 狀態 , 正則表達式 表示為 $\epsilon$ ;

$1$ 狀態 讀取 $(a{b}^{?}a)\cup b$ 正則表達式 跳轉到 $3$ , 正則表達式 表示為 $(a{b}^{?}a)\cup b$ ;

上述兩個正則表達式是串聯關系 , 正則表達式表示為 $\epsilon \cup ((a{b}^{?}a)\cup b)$ , 其中 $\epsilon$ 可以省略 , 最終表示為 $(a{b}^{?}a)\cup b$

2 . 新增加 $S$ 狀態 到 $3$ 狀態之間的跳轉 : $S$ 狀態下讀取 $(a{b}^{?}a)\cup b$ 正則表達式 , 跳轉到 $3$ 狀態 ;

十三、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 2 ) 刪除 狀態 $2,1$ 階段性結果

---

十四、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 4 ) 刪除 狀態 $3$ 信息梳理

---

狀態 $3$ 信息梳理 :

1 . $3$ 狀態信息輸入 :

$S$ 狀態 讀取 $(a{b}^{?}a)\cup b$ 跳轉到 $3$ 狀態 ;

$3$ 狀態 讀取 $(a((a{b}^{?}a)\cup b))\cup (b{b}^{?}a)$ 跳轉到 $3$ 狀態 ;

2 . $3$ 狀態信息輸出 :

$3$ 狀態 讀取 $(a((a{b}^{?}a)\cup b))\cup (b{b}^{?}a)$ 跳轉到 $3$ 狀態 ;

$3$ 狀態讀取 $\epsilon$ 正則表達式 跳轉到 $T$ 狀態 ;

3 . 箭頭信息生成個數 : 自身循環有一個 , 從 $3$ 狀態 自身輸出到輸入 , 外部輸入有 1 條 , 外部輸出 有 $1$ 條 , 需要生成的箭頭信息條數 :

$$外部輸入條數\times 外部輸出條數=1\times 1=1$$

十五、確定性有限自動機 ( DFA ) 轉為 正則表達式 ( 4 ) 刪除 狀態 $3$ : $S$ -> $3$ -> $T$ 生成信息 $S$ -> $T$

---

1 . $S$ -> $3$ -> $T$ 狀態跳轉 :

$S$ 狀態 讀取 $(a{b}^{?}a)\cup b$ 跳轉到 $3$ 狀態 ;

$3$ 狀態 讀取 $(a((a{b}^{?}a)\cup b))\cup (b{b}^{?}a)$ 跳轉到 $3$ 狀態 , 星計算 , 表示成 $(a((a{b}^{?}a)\cup b))\cup (b{b}^{?}a{)}^{?}$

$3$ 狀態讀取 $\epsilon$ 正則表達式 跳轉到 $T$ 狀態 ;

上述 $3$ 個正則表達式是串聯關系 , 正則表達式表示為 :

$$((a{b}^{?}a)\cup b)°((a((a{b}^{?}a)\cup b))\cup (b{b}^{?}a){)}^{?}$$

2 . 新增加 $S$ 狀態 到 $T$ 狀態之間的跳轉 : $S$ 狀態下讀取 $((a{b}^{?}a)\cup b)°((a((a{b}^{?}a)\cup b))\cup (b{b}^{?}a){)}^{?}$ 正則表達式 , 跳轉到 $T$ 狀態 ;

十六、確定性有限自動機 ( DFA ) 轉為 正則表達式 總結

---

由上述示例可知 , 任何 確定性有限自動機 都可以轉為 正則表達式 , 非確定性有限自動機 與 確定性有限自動機 又是等價的 , 因此 有限自動機 都可以轉為 正則表達式 ;

總結

以上是生活随笔為你收集整理的【计算理论】正则语言 ( 推广型的非确定性有限自动机 GNFA | 删除状态 | 确定性有限自动机 转为 正则表达式 )的全部內容，希望文章能夠幫你解決所遇到的問題。

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