構建一個 Σ={0,1} 的 DFA，接受所有包含 0 的字串。

確定性有限自動機 (DFA) 是一個定義為 5 元組的集合，如下所示：

M=(Q, Σ, δ,q0,F)

其中，

• Q：稱為狀態的有限集合。
• Σ：稱為字母表的有限集合。
• δ：Q × Σ → Q 是轉移函式。
• q0 ∈ Q 是起始狀態或初始狀態。
• F：結束狀態或接受狀態。

示例 1

DFA 接受所有以 0 開頭的字串

語言 L= {0,01,001,010,0010,000101,…}

在這個語言中，所有字串都以零開頭。

狀態轉換圖

狀態轉換圖如下所示：

解釋

• 步驟 1 - q0 是初始狀態，輸入 '0' 時，它轉到 q1，這是結束狀態，'0' 字串被接受。
• 步驟 2 - q0 輸入 '1' 時，轉到 q2，這是死狀態，因為對於 q2 沒有路徑可以到達結束狀態。
• 步驟 3 - q1 輸入 '0' 和 '1' 時，都轉到 q1 本身，這是結束狀態。

狀態轉換表

狀態轉換表如下所示：

示例 2

為接受以 '101' 開頭的字串的語言構建 DFA。

• 所有字串都以子字串“101”開頭。
• 則子字串的長度 = 3。

因此，DFA 中最小狀態數 = 3 + 2 = 5。

最小化的 DFA 有五個狀態。

語言 L= {101,1011,10110,101101,.........}

狀態轉換圖如下所示：

解釋

• 步驟 1 - q0 是初始狀態，輸入 '1' 時轉到 q1，輸入 '0' 時導致死狀態。
• 步驟 2 - q1 輸入 '0' 時轉到 q2，輸入 '1' 時轉到死狀態。
• 步驟 3 - q2 輸入 '1' 時轉到 qf，這是結束狀態，輸入 '0' 時轉到死狀態。
• 步驟 4 - qf 是結束狀態，輸入 '1' 和 '0' 時都轉到 qf 本身。

Bhanu Priya

更新於: 2021年6月11日

30K+ 瀏覽量

開啟你的 職業生涯

完成課程獲得認證

開始學習