Not able to convert from NFA to DFA

Question

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:

NFA
_{(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:

Final DFA
_{(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

• Raphael: This is a great example for a basic question that has been posed well, because you include your whole train of thought.

Answer 1

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.

• Anurag Kalia: Oh. So, that is what is creating problem here. Now that I remember, the last time I used this method, there weren't any particular accepting states at all in the table!