設計一個在{0,1}字母表上的DFA，接受1的數量為奇數且0的數量為偶數的字串。

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

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

其中，

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

問題

構造一個接受1的數量為奇數且0的數量為偶數的DFA機器。

解決方案

在字母表 Σ={0,1} 上為這兩個條件分別設計兩個機器。

• DFA 僅接受奇數個 1。

• DFA 僅接受偶數個 0。

這裡，

s1 = 開始

s2=奇數個 1 或開始 11

s3= 開始 11 並被接受，並停留在那裡

s4 = 接受偶數個 0，奇數個 1 以及 0 1 0

s5=偶數個 1，奇數個 0 以及 0 1

s6=奇數個 1 奇數個 0

s7= 奇數個 1 奇數個 0 開始 010

s8=偶數個 0 沒有 1

s0= 奇數個 0 沒有 1

Bhanu Priya

更新於：2021年6月15日

4K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習