1
$\begingroup$

I am currently in a class that deals with DFA's and their minimization. However I believe I have reached a DFA where the method of minimization we were taught doesn't work.

I have the following DFA (in JFLAP)

enter image description here

Using the method given in class I do the following see if their are any non dissimilar states and if so collapse them together.

 | q0  q1  q2  q3  q4  q5 
-------------------------
a| q1  q1  q2  q3  q4  q5  
b| q3  q2  q5  q4  q5  q5

However there are no states where both a and b go to the same state, therefore no collapse states.

However when doing it in JFLAP it gives the following

enter image description here

The only way I can see you getting what JFLAP does is just thinking and having to realize bother q1 and q3 can be joined as well as q2 and q4.

$\endgroup$
  • 1
    $\begingroup$ What's your question? $\endgroup$ – David Richerby Apr 2 '15 at 21:01
  • 1
    $\begingroup$ How is this a DFA given that state initial state q0 has two transitions for an input symbol a? $\endgroup$ – user4275686 Apr 2 '15 at 21:58
  • $\begingroup$ The a near q3 is going from q3 to q3. $\endgroup$ – Zimm3r Apr 2 '15 at 23:58
  • $\begingroup$ @DavidRicherby What is the JFLAP minimization doing that the other method is just missing. $\endgroup$ – Zimm3r Apr 2 '15 at 23:58
6
$\begingroup$

Your method of DFA minimization is incorrect. You start with assuming all states to be different and merge the indistinguishable ones, this may not give the correct minimization. The correct way is to assume all to be same states and separate those which are distinguishable. Look at this for exact algorithm.

$\endgroup$
  • $\begingroup$ Huh ok I'll go back and look at it again. I'm probably making some mistake as i see a lot of similarities to the way the class explained it. Thanks for the information. $\endgroup$ – Zimm3r Apr 2 '15 at 23:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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