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