# Getting minimum DFA for regular expression (11)*+(111)*

(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 Then I followed steps given here to prepare DFA. First I prepared below table to get equivalent DFA steps:

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

Figure 3 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 But I dont get from above table how can I get below minimized DFA as given in the book solution:

Figure 5 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.

• Your table seems to be missing some information. Why states end up being equivalent?
– Raphael
Jan 20, 2015 at 10:44
• 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 Jan 20, 2015 at 10:54
• Why is your state $A$ not accepting? Jan 20, 2015 at 13:19
• As part of $\epsilon$ transition elimination, you should also make the source accepting if the target is accepting. Jan 20, 2015 at 13:45
• 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 Jan 20, 2015 at 14:26

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$.