繪製一個接受以“ab”開頭的字串的DFA。

問題

繪製一個在字母表Σ={a,b}上的狀態轉移圖，該圖接受以'ab'開頭的字串。

解答

確定性有限自動機 (DFA) 的形式化定義如下：

DFA 是一個由 5 元組組成的集合，如下所示：

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

其中，

• Q：有限狀態集。
• Σ：有限字母表集。
• δ：Q × Σ → Q 是轉移函式。
• q0 ∈ Q 是初始狀態。

生成的語言如下所示：

L={ab,aba,abab,……}

狀態轉移圖如下：

這裡，

• D 是一個死狀態。
• D 是一個轉移狀態，它永遠無法逃脫。這種狀態稱為陷阱狀態，也稱為死狀態。

示例 1

• **ab** - q1 在 'a' 上轉移到 q2，q2 在 'b' 上轉移到 qf 以達到最終狀態。因此，ab 被接受。
• **baa** - q1 在 'b' 上轉移到 D 狀態，這是一個死狀態。無法到達最終狀態。因此，baa 未被接受。

轉移表

轉移表如下：

解釋

• **步驟 1** - q1 是初始狀態，輸入 a 時它轉移到狀態 q2，輸入 'b' 時轉移到死狀態。
• **步驟 2** - q2 在 'a' 上轉移到死狀態，在 'b' 上轉移到 qf，這是最終狀態。
• **步驟 3** - qf 是最終狀態，輸入 'a' 和 'b' 時都轉移到 qf 狀態本身。
• **步驟 4** - D 是死狀態，從 D 沒有路徑到任何狀態。

示例 2

設計一個 DFA，它接受字母表 Σ = {a, b} 上的語言，使得 L 是所有以 'aba' 開頭的字串的集合。

所有字串都以子串“aba”開頭。

因此，子串長度 = 3。

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

語言 L= {aba,abaa,abaab,abaaba}

狀態轉移圖如下：

轉移表

轉移表如下：

Bhanu Priya

更新於：2021年6月11日

25K+ 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習