Not able to convert from NFA to DFA

Problem Detail: 

I have a simple problem of making a DFA which accepts all inputs starting with double letters (aa, bb) or ending with double letters (aa, bb), given $\Sigma =\{a, b\}$ is the alphabet set of the given language.

I tried to solve it in a roundabout way by:

1. Generating a regular expression
2. Making its corresponding NFA
3. Using powerset construction to deduce a DFA
4. Minimizing the number of states in DFA

Step 1: Regular expression for given problem is (among countless others):

((aa|bb)(a|b)*)|((a|b)(a|b)*(aa|bb)) 

Step 2: NFA for given expression is:

In Tabular form, NFA is:

State    Input:a     Input:b ->1        2,5         3,5   2        4           -   3        -           4  (4)       4           4   5        5,7         5,6   6        -           8   7        8           -  (8)       -           - 

Step 3: Convert into a DFA using powerset construction:

Symbol, State       +   Symbol, State (Input:a) +   Symbol, State (Input:b)    ->A, {1}         |        B, {2,5}           |        C, {3,5}      B, {2,5}       |        D, {4,5,7}         |        E, {5,6}      C, {3,5}       |        F, {5,7}           |        G, {4,5,6}    (D), {4,5,7}     |        H, {4,5,7,8}       |        G, {4,5,6}      E, {5,6}       |        F, {5,7}           |        I, {5,6,8}      F, {5,7}       |        J, {5,7,8}         |        E, {5,6}    (G), {4,5,6}     |        D, {4,5,7}         |        K, {4,5,6,8}    (H), {4,5,7,8}   |        H, {4,5,7,8}       |        G, {4,5,6}    (I), {5,6,8}     |        F, {5,7}           |        I, {5,6,8}    (J), {5,7,8}     |        J, {5,7,8}         |        E, {5,6}    (K), {4,5,6,8}   +        D, {4,5,7}         +        K, {4,5,6,8} 

Step 4: Minimize the DFA:

I have changed K->G, J->F, I->E first. In the next iteration, H->D and E->F. Thus, the final table is:

  State    +   Input:a     +   Input:b    ->A     |      B        |      C      B     |      D        |      E      C     |      E        |      D     (D)    |      D        |      D     (E)    |      E        |      E 

And diagramatically it looks like:

...which is not the required DFA! I have triple checked my result. So, where did I go wrong?

Note:

• -> = initial state
• () = final state

Asked By : Anurag Kalia

Answered By : rici

You are fine up to step 3 (the DFA) but your minimization is incorrect.

It's clear that the minimized DFA is not right, because both the inputs ba and ab (which are not in the original language, nor are they accepted by the DFA in step 3) lead to final state E.

Looking at your minimization steps, it seems that you have unified final and non-final states; for example J (final) -> F (not final) and I (final) -> E (not final). Merging a final state with a non-final state changes the language accepted by the automaton, leading to the acceptance of incorrect strings as noted above.

Best Answer from StackOverflow

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