構建不以“THE”結尾的字串的DFA

確定性有限自動機 (DFA) 是一個五元組

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

其中，

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

接受不以“THE”結尾的字串

• 觀察給定字串是否以“the”結尾。

• 在字串末尾避免的“the”的不同表示法如下：

     "tHE", "thE", "THE", "ThE", "THe", "The", "tHe" 和 "the"

• 所有這些字串都不被字母表 (A-Z) 接受

令初始狀態為 q0

考慮 4 個狀態 q0、q1、q2 和 q3。

讓我們取一個名為 DFA 的變數，其初始值為 0。

每當發生轉移時，它都會使用與新狀態關聯的數字更新 DFA 的值。

示例

• 如果從狀態 q0 到狀態 q1 發生轉移，則 DFA 的值將更新為 1。

• 如果從狀態 q2 到狀態 q3 發生轉移，則 DFA 的值將更新為 3。

• 以此方式，將此演算法應用於整個字串，如果它到達末尾，則到達狀態 0、1 或 2。因此，我們的字串將被接受。否則，它將不被接受。

案例 1

輸入 - pQdfGTthe

輸出 - 未接受

案例 2

輸入 - ThesdGTYid

輸出 - 接受

Bhanu Priya

更新於： 2021年6月15日

762 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習