[Solved]: Getting minimum DFA for regular expression (11)*+(111)*

Problem Detail: 

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

Asked By : Mahesha999

Answered By : Klaus Draeger

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37411