# Not able to convert from NFA to DFA

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:

(source: livefilestore.com)

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:

(source: livefilestore.com)

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

Note:

• -> = initial state
• () = final state
• This is a great example for a basic question that has been posed well, because you include your whole train of thought. – Raphael Feb 15 '13 at 7:37
• Feels great to be appreciated, thanks! ^^ – Anurag Kalia Feb 15 '13 at 19:55