# 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 '15 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
– Maha
Jan 20 '15 at 10:54
• Why is your state $A$ not accepting? Jan 20 '15 at 13:19
• As part of $\epsilon$ transition elimination, you should also make the source accepting if the target is accepting. Jan 20 '15 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
– Maha
Jan 20 '15 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$.