1
$\begingroup$

Consider the DFA, M=({1, 2, 3, 4, 5, 6}, {a, b}, 1, {2, 5}, δ), whose δ is specified below.

enter image description here

I calculated the following and got unmarked states (5,2) and (6,3)

enter image description here

(6,3) looks okay but there is something wrong with (5,2).It is not deterministic so where did I go wrong?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

States 2 and 5 are distinguishable. We have $(2, 5)\stackrel{b}{\longrightarrow}(1,5)$ and state 1 is a non-final state while state 5 is final. In addition, as HueHang and Amy have noted, $(6, 3)$ is also distinguishable, so the original DFA is already mimimized.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Isn't it $(2,5)\stackrel{b}{\longrightarrow}(1,5)$? And since state $1$ is not final one, states $2$ and $5$ are distinguishable. With this we can further seperate states $3$ and $6$, that is the original DFA is already minimized. $\endgroup$
    – dtt
    Jul 10, 2016 at 16:57
  • $\begingroup$ @HueHang. Good catch. In spite of my attempts to be careful, I get these problems wrong more frequently than I like. $\endgroup$
    – Rick Decker
    Jul 10, 2016 at 17:01
  • $\begingroup$ I agree with @HueHang . If (2,5) are distinguishable (6,3) too should be distinguishable right? Because $(6)\stackrel{a}{\longrightarrow}(2)$ and $(3)\stackrel{a}{\longrightarrow}(5)$ $\endgroup$
    – Amy Cohen
    Jul 10, 2016 at 17:02
  • $\begingroup$ @AmyCohen. Right you are. $\endgroup$
    – Rick Decker
    Jul 10, 2016 at 17:03
  • $\begingroup$ So there is no minimization? :( $\endgroup$
    – Amy Cohen
    Jul 10, 2016 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.