DFA Examples

DFA Examples

The best way to understand DFAs is to build them. Let's walk through several examples, from simple to more complex. Each one follows the same process: define what strings should be accepted, design the states, and verify with test strings.

Example 1: Strings over {0,1} that contain "01"

We need to track whether we've seen a 0 followed by a 1. States: q0 (nothing useful yet), q1 (just saw a 0), q2 (saw "01" — accept). Once we reach q2, we stay there regardless of input.

DFA for strings containing "01":

  q0 --0--> q1 --1--> q2 (accept)
  q0 --1--> q0
  q1 --0--> q1
  q1 --1--> q2
  q2 --0--> q2
  q2 --1--> q2

Trace "10101":
  q0 →(1) q0 →(0) q1 →(1) q2 →(0) q2 →(1) q2 ✓ Accepted

Example 2: Strings with an even number of 1s

States: q0 (even number of 1s seen so far), q1 (odd number of 1s). Each 1 toggles between states. 0s don't change the count. Accept state: q0.

DFA for even number of 1s:

  q0 --0--> q0
  q0 --1--> q1
  q1 --0--> q1
  q1 --1--> q0

Accept: {q0}

Trace "1011":
  q0 →(1) q1 →(0) q1 →(1) q0 →(1) q1 ✗ Rejected (odd 1s)

Trace "1100":
  q0 →(1) q1 →(1) q0 →(0) q0 →(0) q0 ✓ Accepted (even 1s)

Example 3: Strings divisible by 3 in binary

This is a classic. A binary number is divisible by 3 if the sum of its bits weighted by powers of 2 gives a remainder of 0 when divided by 3. States represent the current remainder: q0 (rem 0), q1 (rem 1), q2 (rem 2).

DFA for binary strings divisible by 3:

  q0 --0--> q0
  q0 --1--> q1
  q1 --0--> q2
  q1 --1--> q0
  q2 --0--> q1
  q2 --1--> q2

Accept: {q0}

Trace "110" (= 6 in decimal):
  q0 →(1) q1 →(1) q0 →(0) q0 ✓ Accepted (6 % 3 == 0)

Example 4: Strings starting with 0 and ending with 1

States: q0 (start), q1 (saw leading 0), q2 (starts with 1 — dead path for this language), q3 (started with 0 and ends with 1). If the first symbol is 1, we go to q2 (trap state). Otherwise we proceed tracking the last symbol.

DFA for strings starting with 0 and ending with 1:

  q0 --0--> q1
  q0 --1--> q2 (trap)
  q1 --0--> q1
  q1 --1--> q3 (accept)
  q2 --0--> q2
  q2 --1--> q2
  q3 --0--> q1
  q3 --1--> q3

Trace "01": q0 →(0) q1 →(1) q3 ✓
Trace "001": q0 →(0) q1 →(0) q1 →(1) q3 ✓
Trace "1": q0 →(1) q2 ✗
Trace "00": q0 →(0) q1 →(0) q1 ✗