Chapter 05 of 34

Designing DFAs: Solved Problems

Knowing the definition of a DFA is one thing; building one for a given language in an exam, in five minutes, without mistakes, is another. The good news is that almost every DFA question in university papers and GATE belongs to a small number of patterns: starts with, ends with, contains, counting, modulo, divisibility, position from the end, and combinations of these. Each pattern has a standard design idea and a predictable number of states.

This chapter is a workbook. We first fix a design method, then solve eleven typical problems step by step, each with a transition table, a text diagram, traces and the reasoning behind every transition. At the end, a table gives the minimum number of states for each pattern. Every DFA in this chapter was simulated and compared against its language definition on all strings of length 0 to 10, and each was checked to be minimal (no two states equivalent). We use the definitions from Deterministic Finite Automata (DFA).


The Design Method

  1. Write down examples. List a few short strings that must be accepted and a few that must be rejected, including ε. Edge cases found now save marks later.

  2. Decide what to remember. Ask: "after reading part of the input, what is the least information I need to finish the job?" Each possible value of that information is one state. Write the meaning of every state in words.

  3. Fill the transition table. For each state and each symbol, ask: "if the information so far is X and I now read this symbol, what is the new information?" The meanings make every entry obvious.

  4. Mark start and final states. The start state means "nothing read yet". Final states are those whose meaning says "accept if the input stops here".

  5. Add a dead state if needed, so the DFA is complete.

  6. Test. Trace ε, your accepted examples and your rejected examples. Tricky ones are strings with overlaps (like aaba when looking for aba).

Throughout, Σ = {a, b} unless stated otherwise, → marks the start state and * marks final states.


Problem 1: Strings That Start With "ab"

Accept: ab, aba, abbb. Reject: ε, a, b, ba, aab.

What to remember: how much of the required prefix we have matched, or that we have already failed.

  • q0: nothing read yet.

  • q1: read "a" so far (on track).

  • q2: read "ab" at the start; accept whatever follows.

  • qd: the prefix was wrong; reject whatever follows.

δ

a

b

→ q0

q1

qd

q1

qd

q2

* q2

q2

q2

qd

qd

qd

  --> ( q0 ) --a--> ( q1 ) --b--> (( q2 )) --+
         |             |              ^        | a, b
         b             a              +--------+
         |             |
         +---> ( qd ) <+
                ^    |
                +----+ a, b

Minimum states: 4. In general, "starts with a given string of length n" needs n + 2 states: n + 1 for the matched prefix lengths 0..n, plus a dead state.


Problem 2: Strings That Contain "aba"

Accept: aba, aaba, babab, abaa. Reject: ε, ab, abba, bbb.

What to remember: the longest suffix of the input so far that is also a prefix of "aba" (0, 1, 2 symbols matched), or that we have already seen aba.

  • q0: no progress. q1: input ends with "a". q2: input ends with "ab". q3: "aba" has occurred (final, accepting sink).

δ

a

b

→ q0

q1

q0

q1

q1

q2

q2

q3

q0

* q3

q3

q3

       b            a                        a, b
     +---+        +---+                     +----+
     |   v        |   v                     |    v
  --> ( q0 ) --a--> ( q1 ) --b--> ( q2 ) --a--> (( q3 ))
         ^                          |
         +------------b-------------+

The two entries that need thought are the mismatch moves:

  • q1 on a → q1, not q0. After "aa", the last a can still start "aba". Sending it to q0 would wrongly reject aaba.

  • q2 on b → q0. After "abb", no suffix (b, bb, abb) is a prefix of "aba", so all progress is lost.

Trace of aaba: q0 →a→ q1 →a→ q1 →b→ q2 →a→ q3. Accepted. The general rule for a mismatch: go to the state for the longest suffix of (what you have matched + the new symbol) that is a prefix of the pattern. This is exactly the idea behind the KMP string-matching algorithm.

Minimum states: 4; in general "contains a given substring of length n" needs n + 1 states.


Problem 3: Strings That End With "abb"

Accept: abb, aabb, babb, abbabb. Reject: ε, ab, abba, bbb.

This looks like Problem 2, but there is no accepting sink: after "abb" the input may continue and spoil the ending. States mean "the longest suffix that is a prefix of abb": q0 (none), q1 (a), q2 (ab), q3 (abb, final).

δ

a

b

→ q0

q1

q0

q1

q1

q2

q2

q1

q3

* q3

q1

q0

Why these mismatch entries? From q2 ("…ab") an a gives "…aba", whose longest useful suffix is "a", so q1. From q3 ("…abb") an a gives "…abba", again ending in a, so q1; a b gives "…abbb", with no useful suffix, so q0. Notice that every state goes to q1 on a, because any string ending in a ends with the first symbol of the pattern.

ababb  : q0 -a-> q1 -b-> q2 -a-> q1 -b-> q2 -b-> q3          ACCEPT
abbabb : q0 -a-> q1 -b-> q2 -b-> q3 -a-> q1 -b-> q2 -b-> q3  ACCEPT
aabab  : q0 -a-> q1 -a-> q1 -b-> q2 -a-> q1 -b-> q2          REJECT

Minimum states: 4; "ends with a given string of length n" needs n + 1 states.


Problem 4: Length Leaves Remainder 1 When Divided by 3

L = {w : |w| mod 3 = 1} = {a, b, aaaa, abab, ...}. The symbol does not matter, only the count of symbols modulo 3. States r0, r1, r2 (remainder so far), start r0, final r1.

δ

a

b

→ r0

r1

r1

* r1

r2

r2

r2

r0

r0

  --> ( r0 ) --a,b--> (( r1 )) --a,b--> ( r2 )
         ^                                  |
         +---------------a,b----------------+

A cycle of length 3, no dead state. Changing the final state changes the remainder: final r0 gives "length divisible by 3" (which accepts ε). |w| mod n = k needs exactly n states.


Problem 5: Exactly, At Least, At Most Two a's

All three use the same idea: count the a's, but stop counting once the exact number no longer matters. Let ci mean "i a's seen so far"; b's never change the count.

δ

a

b

Exactly 2

At most 2

→ c0

c1

c0

final

c1

c2

c1

final

c2

cd

c2

final

final

cd (3 or more)

cd

cd

  • Exactly 2 a's: 4 states, final {c2}, cd is a dead state.

  • At most 2 a's: the same 4 states, final {c0, c1, c2}. (It is the complement of "at least 3".)

  • At least 2 a's: once we have 2, more a's do not matter, so c2 loops on both symbols and no cd is needed: 3 states c0, c1, c2, final {c2}.

For a general n: exactly n → n + 2 states, at most n → n + 2, at least n → n + 1. The same counts hold for "length exactly / at most / at least n".


Problem 6: Even Number of a's AND Odd Number of b's (Product Construction)

Two independent conditions. Design one small DFA for each, then run them in parallel:

  • DFA A tracks parity of a's: states Ea, Oa.

  • DFA B tracks parity of b's: states Eb, Ob.

A state of the combined DFA is a pair (state of A, state of B). We write EO for (even a's, odd b's), and so on. Reading a flips the first letter; reading b flips the second.

δ

a

b

→ EE

OE

EO

* EO

OO

EE

OE

EE

OO

OO

EO

OE

                a
     --> ( EE ) <-----> ( OE )
           ^                ^
         b |              b |        a moves horizontally
           v                v        b moves vertically
        (( EO )) <-----> ( OO )
                    a

Trace of abab: EE →a→ OE →b→ OO →a→ EO →b→ EE. Reject (2 a's, 2 b's: b count is even). Trace of aab: EE → OE → EE → EO. Accept.

The General Product Construction

Given DFAs M1 = (Q1, Σ, δ1, p0, F1) and M2 = (Q2, Σ, δ2, q0, F2), the product DFA has states Q1 × Q2, start (p0, q0) and δ((p, q), a) = (δ1(p, a), δ2(q, a)). Only the final states depend on the operation.

Language wanted

Final states of the product

In Problem 6 terms

L1 ∩ L2 (AND)

pairs where both are final: F1 × F2

{EO}

L1 ∪ L2 (OR)

pairs where at least one is final

{EE, EO, OO}

L1 - L2

first final, second not: F1 × (Q2 - F2)

{EE}

Symmetric difference (XOR)

exactly one final

{EE, OO}

So the product of an m-state and an n-state DFA has at most m × n states. For conditions like "|w|a mod m = i and |w|b mod n = j", all m × n states are needed. Both M1 and M2 must be complete for the OR and difference cases to work.


Problem 7: Binary Numbers Divisible by 3

Σ = {0, 1}. Read a binary number from the most significant bit and accept if its value is divisible by 3. Convention: ε has value 0 and leading zeros are allowed (so 0, 00, 011 are fine inputs).

What to remember: not the number (it can be huge), only its remainder mod 3. When we read one more bit b after a number with value v, the new value is 2v + b. Taking remainders:

new remainder = (2 × old remainder + b) mod 3

So three states 0, 1, 2 (the remainder), start 0, final 0:

δ

0

1

→ * 0

0

1

1

2

0

2

1

2

        0                                     1
      +---+                                 +---+
      |   v        1             0          |   v
  --> (( 0 )) <-------> ( 1 ) <-------> ( 2 )
                  1             0
   (0 --1--> 1, 1 --1--> 0, 1 --0--> 2, 2 --0--> 1)
110  (=6) : 0 -1-> 1 -1-> 0 -0-> 0               ACCEPT
1001 (=9) : 0 -1-> 1 -0-> 2 -0-> 1 -1-> 0        ACCEPT
111  (=7) : 0 -1-> 1 -1-> 0 -1-> 1               REJECT  (7 mod 3 = 1)

Check one transition: in state 2 reading 1 gives (2 × 2 + 1) mod 3 = 5 mod 3 = 2. Correct.

Divisible by 5

The same formula with mod 5 gives 5 states:

δ

0

1

→ * 0

0

1

1

2

3

2

4

0

3

1

2

4

3

4

For base-10 input the rule becomes (10 × r + d) mod k, and for base-b input (b × r + d) mod k. This "remainder automaton" is one of the most frequently asked DFA designs.

Careful: Minimum States for Divisibility

The remainder DFA for "divisible by k" always has k states, but it is not always minimal. For k = 4, a binary number is divisible by 4 exactly when it ends in 00 (or is ε, 0), which needs only 3 states. We computed the true minimum for k = 1 to 16:

k

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

min states

1

2

3

3

5

4

7

4

9

6

11

5

13

8

15

5

The pattern: write k = 2j × m with m odd. Then the minimal DFA (binary input, MSB first) has m + j states. For odd k that is simply k; for k = 6 = 2 × 3 it is 3 + 1 = 4; for k = 8 it is 1 + 3 = 4.


Problem 8: The Second Symbol From the Right Is a

L = {w : |w| ≥ 2 and the second-last symbol is a}. Accept: aa, ab, bab, aab. Reject: ε, a, b, ba, abb.

The machine cannot know which symbol is "second from the end" until the input ends, so it must always remember the last two symbols read. There are 4 possibilities: bb, ba, ab, aa. Treat "not enough symbols yet" like b (since a missing symbol is certainly not a), so the start state is bb. On reading c in state xy, move to yc.

δ

a

b

→ bb

ba

bb

ba

aa

ab

* ab

ba

bb

* aa

aa

ab

Final states are those whose first letter is a. Trace bab: bb →b→ bb →a→ ba →b→ ab, accept. Trace abb: bb → ba → ab → bb, reject.

For the n-th symbol from the right, the DFA must remember the last n symbols, giving 2n states, and this is provably the minimum (any two different length-n windows can be told apart by some continuation). Compare this with the n-th symbol from the left, which needs only n + 2 states. This exponential gap is the classic example where an NFA is far smaller than any DFA, as you will see in Nondeterministic Finite Automata (NFA).


Problem 9: Strings With No Two Consecutive a's

L = {w : aa is not a substring of w}. Easiest route: build "contains aa" (3 states, like Problem 2) and complement it by swapping final states.

δ

a

b

Meaning

→ * q0

q1

q0

no aa yet, last symbol not a (or nothing read)

* q1

qd

q0

no aa yet, last symbol is a

qd

qd

qd

aa seen: dead

Variant: "every a is immediately followed by b" uses the same transitions but only q0 is final, because a string ending in a (state q1) has an a with nothing after it. One changed final state, a different language: always reread the question.


Problem 10: Starts and Ends With the Same Symbol

L = {w : |w| ≥ 1 and the first symbol equals the last}. Accept: a, b, aba, bb, abba. Reject: ε, ab, ba, aab.

We must remember the first symbol forever, and the last symbol as it changes. The machine splits into two halves after the first symbol:

State

Meaning

a

b

→ s

nothing read

A1

B1

* A1

started with a, last is a

A1

A2

A2

started with a, last is b

A1

A2

* B1

started with b, last is b

B2

B1

B2

started with b, last is a

B2

B1

                  +-a-+                      +-b-+
                  |   v                      |   v
            a --> (( A1 )) -------b-------> ( A2 )
           /               <------a--------
  --> ( s )
           \               -------a------->
            b --> (( B1 ))                  ( B2 )
                  |   ^    <------b--------  |   ^
                  +-b-+                      +-a-+

Minimum states: 5. Note that s is not final, because ε has no first symbol. If the question says "starts and ends with different symbols", keep the same transitions and make A2 and B2 final instead.


Problem 11 (GATE Style): Number of 0s Divisible by 2 and Number of 1s Divisible by 3

Σ = {0, 1}. Product of a 2-state counter for 0s and a 3-state counter for 1s: states (i, j) with i = |w|0 mod 2 and j = |w|1 mod 3. Reading 0 changes i; reading 1 changes j.

δ

0

1

→ * (0,0)

(1,0)

(0,1)

(0,1)

(1,1)

(0,2)

(0,2)

(1,2)

(0,0)

(1,0)

(0,0)

(1,1)

(1,1)

(0,1)

(1,2)

(1,2)

(0,2)

(1,0)

Minimum number of states: 2 × 3 = 6. All six are needed: any two different (i, j) pairs can be distinguished by appending suitable 0s and 1s.


Cheat Sheet: Minimum Number of States

For Σ = {a, b} (the counts include the dead state when one is needed). Every row was confirmed by computing the minimal DFA for n = 1 to 4.

Language

Minimum states

Dead state?

|w| = n

n + 2

Yes

|w| ≥ n

n + 1

No

|w| ≤ n

n + 2

Yes

|w| mod n = k

n

No

|w|a = n / ≥ n / ≤ n

n + 2 / n + 1 / n + 2

Yes / No / Yes

Starts with a fixed string of length n

n + 2

Yes

Contains a fixed substring of length n

n + 1

No (accepting sink)

Ends with a fixed string of length n

n + 1

No

n-th symbol from the left is a

n + 2

Yes

n-th symbol from the right is a

2n

No

|w|a mod m = i AND |w|b mod n = j

m × n

No

Binary value divisible by k = 2j·m (m odd)

m + j (k if k is odd)

No

These are shortcuts for checking your answer, not a replacement for designing. If the language combines patterns, design it (or use a product) and then count. DFA Minimization shows how to prove that a DFA is minimal.


Common Mistakes

  • Resetting to the start state on every mismatch in "contains" and "ends with" problems. After "aa" while looking for "aba", keep the last a. Always fall back to the longest suffix that is still a prefix of the pattern.

  • Making "contains" and "ends with" DFAs identical. "Contains" has an accepting sink; "ends with" must leave the final state when the ending is spoiled.

  • Forgetting the dead state in starts-with, exactly-n and at-most-n problems, and then giving an answer one too small.

  • Getting ε wrong. "Divisible by 3" and "length divisible by n" accept ε; "starts and ends with the same symbol" and "second from right is a" do not.

  • Using AND final states for an OR question in the product construction (or vice versa). The transitions are the same; only F changes.

  • Assuming the remainder DFA for "divisible by k" is always minimal. It is for odd k; for even k it can be smaller.

  • Testing only accepted strings. A DFA that accepts everything passes that test. Always trace some strings that must be rejected.


GATE-Style Questions

Q1. Minimum number of states in a DFA over {a, b} accepting strings whose length is exactly 3?

n + 2 = 5: four states for lengths 0, 1, 2, 3 (only 3 final) plus a dead state for length 4 or more.

Q2. Minimum number of states in a DFA over {0, 1} that accepts binary numbers divisible by 5?

5 is odd, so 5 states: the remainder DFA with δ(r, b) = (2r + b) mod 5 is already minimal.

Q3. Minimum number of states for binary numbers divisible by 6?

6 = 2 × 3, so 3 + 1 = 4 states, not 6. (A number is divisible by 6 if and only if it is divisible by 3 and ends in 0.)

Q4. Minimum DFA states for strings over {a, b} whose 3rd symbol from the right end is a?

23 = 8. The DFA must remember the last three symbols, and all 8 windows are distinguishable.

Q5. A DFA accepts strings over {a, b} that contain "abab" as a substring. How many states does the minimal DFA have?

n + 1 = 5 (matched 0, 1, 2, 3 symbols, plus the accepting sink).

Q6. Using the product construction, how many states can the DFA for "even number of a's AND number of b's divisible by 3" have at most, and is that the minimum?

2 × 3 = 6, and all 6 are needed, so 6 is the minimum.

Q7. In Problem 3 (ends with abb), what is δ̂(q0, babba)?

q0 →b→ q0 →a→ q1 →b→ q2 →b→ q3 →a→ q1. So δ̂(q0, babba) = q1, and the string is rejected.

Q8. Minimum states for strings over {a, b} that start with a and end with b?

4: start; dead (first symbol b); "started with a, last symbol a" (non-final); "started with a, last symbol b" (final).


Summary

  • Design a DFA by deciding what must be remembered, giving each state a written meaning, then filling the table from those meanings.

  • Starts with: chain plus dead state (n + 2). Contains: KMP-style chain with an accepting sink (n + 1). Ends with: same chain, final state can be left (n + 1).

  • Counting stops once the exact count stops mattering; modulo conditions give cycles of n states.

  • The product construction combines DFAs for AND, OR, difference and XOR by choosing different final states.

  • Divisibility: new remainder = (base × old + digit) mod k. Minimal size is k for odd k and m + j for k = 2jm.

  • n-th symbol from the right needs 2n DFA states, a first sign of why NFAs are useful, the topic of the next chapter, Nondeterministic Finite Automata (NFA).