構建任何給定有限自動機的最小DFA。

問題

為以下自動機構建一個最小狀態DFA：

解答

我們首先為給定的有限自動機構建一個狀態轉移表：

Q={q0,q1,q2,q3,q4,q5,q6,q7}

Q01={q2} 和 Q02={q0,q1,q2,q3,q4,q5,q6,q7}

S0={{q2} {q0,q1,q2,q3,q4,q5,q6,q7}}

考慮集合 {q0,q1,q2,q3,q4,q5,q6,q7}

{q2} {q0,q1,q3,q5,q6,q7}

{q2} {q0,q4,q6} {q1,q3,q5,q7}

{q2} {q0,q4} {q6} {q1,q3,q5,q7}

{q2}{q0,q4}{q6}{q1,q7}{q3,q5}

最小化後的狀態如下：

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

Q¹= {[q2],[q0,q4],[q6],[q1,q7],[q3,q5]}

qo¹= {[q0,q4]}

F¹= {[q2]}

狀態轉移表

現在狀態轉移表如下：

狀態轉移圖如下：

Bhanu Priya

更新於：2021年6月12日

5K+ 瀏覽量

開啟你的職業生涯

透過完成課程獲得認證

開始學習