# 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! ^^ Feb 15 '13 at 19:55

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.