設計一個接受奇數個 0 或偶數個 1 的 DFA 機器

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

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

其中，

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

問題

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

解決方案

針對字母表 Σ={0,1} 上的兩個條件設計兩個獨立的機器 -

• 僅接受奇數個 0 的 DFA

• 僅接受偶數個 1 的 DFA

在字母表 Σ={0,1} 上僅接受奇數個 1 的 DFA

    語言 L= {1,10,1110,1011,10101,100101,….}

在字母表 Σ={0,1} 上僅接受偶數個 1 的 DFA

    語言 L= {11,101,11110,10111,101101,1001011,….}

現在合併兩個狀態轉換圖以生成一個接受奇數個 0 或偶數個 1 的機器

Bhanu Priya

更新於： 2021年6月15日

9K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習