0
$\begingroup$

(sorry beforehand I know putting scanned diagrams may seem not-so-professional but this problem is sticking for long and its interesting too)

The language corresponding to given regex seems to accepts all strings of 1's with length in multiple of 2 or 3 (i.e.4,6,8,9,10,12,...)

I prepared following NFA first:

Figure 1 enter image description here

Then I followed steps given here to prepare DFA. First I prepared below table to get equivalent DFA steps:

Figure 2 enter image description here

Then I prepared below DFA, which seems to be quite correct.

Figure 3 enter image description here

Next to get equivalent states I followed table filling algorithm as explained [here] (http://books.google.co.in/books?id=tzttuN4gsVgC&lpg=PP1&pg=PA144#v=onepage&q&f=false) and formed below:

(cross between every intersecting column and row indicates two intersecting states are distinguishable / not equivalent)

Figure 4 enter image description here

But I dont get from above table how can I get below minimized DFA as given in the book solution:

Figure 5 enter image description here

So in the solution of the textbook, their is one less state (total 6) than my dfa in figure 3 (which has 7 states). I should be able to derive the same (equivalent 6-state dfa) from above triangular table.

Improve this question
$\endgroup$
7
  • $\begingroup$ Your table seems to be missing some information. Why states end up being equivalent? $\endgroup$
    – Raphael ♦
    Jan 20, 2015 at 10:44
  • $\begingroup$ Nope crosses in that triangular table means the intersecting states are distinguishable / not equivalent , that is all states are distinguishable from each other and I feel that's correct since if you look at allowed lengths of 1s no state can be equivalent, though just guessing. For procedure of putting those crosses refer link $\endgroup$
    – Mahesha999
    Jan 20, 2015 at 10:54
  • 3
    $\begingroup$ Why is your state $A$ not accepting? $\endgroup$
    – Klaus Draeger
    Jan 20, 2015 at 13:19
  • 2
    $\begingroup$ As part of $\epsilon$ transition elimination, you should also make the source accepting if the target is accepting. $\endgroup$
    – Klaus Draeger
    Jan 20, 2015 at 13:45
  • 1
    $\begingroup$ yep maan you are correct, I made a silly mistake, A should be accepting state, now realizing :'( , just ignored to check my original nfa since it generated correct dfa accepting (11)* +(111)* in figure 3, but it was the reason for wrong minimization output $\endgroup$
    – Mahesha999
    Jan 20, 2015 at 14:26

1 Answer 1

Reset to default
4
$\begingroup$

The problem is that you did not make state $A$ accepting during $\epsilon$ transition elimination. Since it has $\epsilon$ transitions to accepting states, you should have done so. As a result, the automaton you obtain doesn't accept the empty word as it should. If you fix this, minimization then merges $A$ with $B,D$.

Improve this answer
$\endgroup$

Your Answer

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

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