Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

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

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

Note:

  • -> = initial state
  • () = final state
share|improve this question
1  
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

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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! –  Anurag Kalia Feb 15 '13 at 19:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.