构建任何给定有限自动机的最小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+ 浏览量

开启你的职业生涯

通过完成课程获得认证

开始学习