文章目錄

• 一、自動機設計
• 二、自動機設計 1
• 三、自動機設計 2
• 四、自動機設計 3
• 五、自動機設計技巧

一、自動機設計

---

設計自動機 : 之前是根據給定的自動機 , 找到自動機所能識別的語言 ; 現在是 給定語言 , 設計出能識別該語言的自動機 ;

自動機設計需求 : 設計一個又窮自動機 $M$ , 滿足以下的給定的語言要求 ; 即語言已經存在 , 求自動機 ;

1 . 自動機語言字符集 : $\Sigma =\{0,1\}$ , 字符集是 $0$ 和 $1$ 組成 , 該自動機語言由 $0,1$ 組成 , 如 $0101$ , $100111$ 等 ;

2 . 自動機語言描述 :

① 自動機語言集合 : 自動機 $M$ 所能接受的字符串都放在集合 $A$ 中 , 集合 $A$ 就是該自動機語言 ;

② 自動機語言要求 : 自動機 $M$ 的語言 $A$ 集合 中的字符串中都有 奇數 個 $1$ ;

3 . 接受狀態 與 非接受狀態 : 根據上述自動機語言要求 , 定義接受狀態和非接受狀態 ;

① 接受狀態 : 如果當前輸入的字符串中 , 含有奇數個 $1$ 那么當前狀態是 接受狀態 ;

② 非接受狀態 : 如果當前輸入字符串中 , 有偶數個 $1$ , 那么當前的狀態就是 非接受狀態 ;

參考博客 :

• 【計算理論】確定性有窮自動機 ( 自動機組成 | 自動機語言 | 自動機等價 )
• 【計算理論】自動機設計 ( 設計自動機 | 確定性自動機設計示例 | 確定性與非確定性 | 自動機中的不確定性 )

二、自動機設計 1

---

設計 $\mathrm{L}=\{\mathrm{w}|\mathrm{w}以1開始,以0結束\}$ 語言對應的 確定性有限自動機 ; 字母表為 $\{0,1\}$ ;

1 . 開始狀態 : 首先要考慮 第一個狀態 ${\mathrm{q}}_1$ 是 接受狀態 還是非接受狀態 ,

如果是 接受狀態 , 使用雙圈表示 ,

如果是 非接受狀態 , 使用單圈表示 ;

第一個狀態時 , 還沒有讀取字符 , 不符合 $\mathrm{L}$ 語言要求 , 使用單圈表示 ;

2 . 開始狀態 ${\mathrm{q}}_1$ 狀態指令 : 讀取的第一個字符必須是 $1$ , 讀取 $1$ 字符 后進入 ${\mathrm{q}}_2$ 狀態 ;

如果讀取 $0$ 字符 , 則不符合 $\mathrm{L}$ 語言要求 , 卡在開始狀態 , 自動機停機 ;

3 . ${\mathrm{q}}_2$ 狀態指令 : 可以讀取 $0,1$ 字符 ,

讀取 $0$ 字符即進入 ${\mathrm{q}}_3$ 接受狀態 ,

讀取 $1$ 字符后回到 ${\mathrm{q}}_2$ 非接受狀態 ;

4 . ${\mathrm{q}}_3$ 狀態指令 : 可以讀取 $0,1$ 字符 ,

讀取 $0$ 字符還是進入本 ${\mathrm{q}}_3$ 接受狀態 ,

讀取 $1$ 字符后回到 ${\mathrm{q}}_2$ 非接受狀態 ;

自動機設計如下 :

三、自動機設計 2

---

設計 $\mathrm{L}=\{\mathrm{w}|\mathrm{w}至少含有3個1\}$ 語言對應的 確定性有限自動機 ; 字母表為 $\{0,1\}$ ;

1 . 開始狀態 : 首先要考慮 第一個狀態 ${\mathrm{q}}_1$ 是 接受狀態 還是非接受狀態 ,

如果是 接受狀態 , 使用雙圈表示 ,

如果是 非接受狀態 , 使用單圈表示 ;

第一個狀態時 , 還沒有讀取字符 , 肯定沒有 $3$ 個 $1$ , 不符合 $\mathrm{L}$ 語言要求 , 使用單圈表示 ;

2 . 開始狀態 ${\mathrm{q}}_1$ 狀態指令 :

如果讀取 $0$ 字符 , 原地不動 , 保持 ${\mathrm{q}}_1$ 狀態不變 ;

如果讀取 $1$ 字符 , 則跳轉到 ${\mathrm{q}}_2$ 狀態 ;

3 . ${\mathrm{q}}_2$ 狀態指令 :

如果讀取 $0$ 字符 , 原地不動 , 保持 ${\mathrm{q}}_2$ 狀態不變 ;

如果讀取 $1$ 字符 , 則跳轉到 ${\mathrm{q}}_3$ 狀態 ;

4 . ${\mathrm{q}}_3$ 狀態指令 :

如果讀取 $0$ 字符 , 原地不動 , 保持 ${\mathrm{q}}_3$ 狀態不變 ;

如果讀取 $1$ 字符 , 則跳轉到 ${\mathrm{q}}_4$ 狀態 ;

5 . ${\mathrm{q}}_4$ 狀態指令 : 截止到此處 , 前面已經讀取了 $3$ 個 $1$ 字符 , 達到接受狀態標準 ;

自動機設計如下 :

四、自動機設計 3

---

設計 $\mathrm{L}=\{\mathrm{w}|\mathrm{w}含有子串0101\}$ 語言對應的 確定性有限自動機 ; 字母表為 $\{0,1\}$ ;

分析 : $\mathrm{L}$ 語言中每個字符串的形式為 $\mathrm{x}0101\mathrm{y}$ , 其中 $\mathrm{x},\mathrm{y}$ 可以是空字符 , 也可以是若干個字符 ;

1 . 開始狀態 : 首先要考慮 第一個狀態 ${\mathrm{q}}_1$ 是 接受狀態 還是非接受狀態 ,

如果是 接受狀態 , 使用雙圈表示 ,

如果是 非接受狀態 , 使用單圈表示 ;

第一個狀態時 , 還沒有讀取字符 , 肯定沒有讀取到 $0101$ 子串 , 不符合 $\mathrm{L}$ 語言要求 , 使用單圈表示 ;

起始狀態 ${\mathrm{q}}_1$

讀取完第一個 子串 字符 $0$ 后的狀態 ${\mathrm{q}}_2$

讀取完第二個 子串 字符 $1$ 后的狀態 ${\mathrm{q}}_3$

讀取完第三個 子串 字符 $0$ 后的狀態 ${\mathrm{q}}_4$

讀取完第四個 子串 字符 $1$ 后的狀態 ${\mathrm{q}}_5$

2 . 開始狀態 ${\mathrm{q}}_1$ 狀態指令 :

如果讀取 $1$ 字符 , 不符合子串起始字符 $0$ , 原地不動 , 保持 ${\mathrm{q}}_1$ 狀態不變 ;

如果讀取 $0$ 字符 , 則跳轉到 ${\mathrm{q}}_2$ 狀態 ;

3 . ${\mathrm{q}}_2$ 狀態指令 :

如果讀取 $0$ 字符 , 不符合子串第二個字符 $1$ , 但是這個字符有可能是 $0101$ 子串第一個字符 , 保持 ${\mathrm{q}}_2$ 狀態不變 , 將該子串當做第一個字符 ;

如果讀取 $1$ 字符 , 則跳轉到 ${\mathrm{q}}_3$ 狀態 ;

4 . ${\mathrm{q}}_3$ 狀態指令 :

如果讀取 $1$ 字符 , 不符合子串第三個字符 $0$ , 直接跳轉到起始狀態 ${\mathrm{q}}_1$ , 繼續讀取后續字符 ;

如果讀取 $0$ 字符 , 則跳轉到 ${\mathrm{q}}_4$ 狀態 ;

5 . ${\mathrm{q}}_4$ 狀態指令 :

如果讀取 $0$ 字符 , 不符合子串第四個字符 $1$ , 可以當做第一個字符 , 這里跳轉到 ${\mathrm{q}}_2$ 狀態 ;

如果讀取 $1$ 字符 , 則跳轉到 ${\mathrm{q}}_5$ 狀態 ;

6. ${\mathrm{q}}_5$ 狀態指令 : 此時已經讀取完 $0101$ 子串 , 達到接受狀態 ; 不管后續讀取什么字符 , 都保持不變即可 ;

如果讀取 $0$ 字符 , 保持本狀態不變 ;

如果讀取 $1$ 字符 , 保持本狀態不變 ;

自動機設計如下 : 下圖中從左到右就是 ${\mathrm{q}}_1,{\mathrm{q}}_2,{\mathrm{q}}_3,{\mathrm{q}}_4,{\mathrm{q}}_5$ 五個狀態 ;

五、自動機設計技巧

---

可以先將主干設計出來 , 然后再考慮每個狀態的其它分支字符 , 只要合理即可 ;

設計出的自動機可能不是最右的 ;

總結

以上是生活随笔為你收集整理的【计算理论】计算理论总结 ( 自动机设计 ) ★★的全部內容，希望文章能夠幫你解決所遇到的問題。

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