Designing DFAs: memory, complement and product

Intermediate

Introduction

Reading a DFA is easy; designing one is a skill. The trick is to ask one question before drawing anything: what is the least the machine must remember about the input so far to give the right answer at the end? Once that is clear, each possible memory becomes a state, and the moves almost write themselves.

This lesson also shows that DFAs can be combined like building blocks. If you have machines for two languages, you can mechanically build machines for "not L", "L and M" and "L or M".

How it works

Designing by memory. For "contains ab", the machine only needs to know one of three things: it has not started a match, it has just seen an a, or it has already seen ab. Those are three states: s, A and f. On b from A it moves to f, and f loops on everything, because once ab has appeared the answer cannot change.

Dead states. Every DFA must have a move for every state and symbol. When a prefix can never lead to acceptance, the move goes to a dead state, a non-accepting state that loops to itself. A DFA with every move present is called complete.

Complement. To accept exactly the strings that M rejects, keep M and swap its accepting and non-accepting states. This works only on a complete DFA: if a move were missing, the string would be rejected by both machines.

delta = {("s", "a"): "A", ("s", "b"): "s", ("A", "a"): "A", ("A", "b"): "f", ("f", "a"): "f", ("f", "b"): "f"}
accept = {"f"}
states = {"s", "A", "f"}
flipped = states - accept
for w in ["ab", "ba", "bbb"]:
    state = "s"
    for c in w:
        state = delta[(state, c)]
    print(w, "contains ab:", state in accept, "| complement:", state in flipped)
Open in compiler

Product construction. To run two DFAs at the same time, make each new state a pair (state of M1, state of M2). On a symbol, both halves move: δ((p, q), c) = (δ1(p, c), δ2(q, c)). The new start state is (start1, start2). The choice of accepting pairs decides what the product does:

  • intersection (L1 ∩ L2): pairs where both halves accept;
  • union (L1 ∪ L2): pairs where at least one half accepts.

With m and n states, the product has m × n states. Because these constructions always produce a DFA, regular languages are closed under complement, intersection and union.

Syntax

flipped = states - accept                         # complement (complete DFA)
delta[((p, q), c)] = (d1[(p, c)], d2[(q, c)])     # product move
both  = {(p, q) for p in F1 for q in F2}          # intersection
either = {(p, q) for p in Q1 for q in Q2 if p in F1 or q in F2}   # union

Example

from itertools import product

even_a = {("E", "a"): "O", ("E", "b"): "E", ("O", "a"): "E", ("O", "b"): "O"}
ends_b = {("N", "a"): "N", ("N", "b"): "Y", ("Y", "a"): "N", ("Y", "b"): "Y"}


def product_dfa(d1, d2, states1, states2, alphabet):
    delta = {}
    for s1, s2 in product(states1, states2):
        for c in alphabet:
            delta[((s1, s2), c)] = (d1[(s1, c)], d2[(s2, c)])
    return delta


delta = product_dfa(even_a, ends_b, ["E", "O"], ["N", "Y"], "ab")
start = ("E", "N")
both = {("E", "Y")}


def accepts(word):
    state = start
    for c in word:
        state = delta[(state, c)]
    return state in both


print("states:", len({s for s, _ in delta}))
for w in ["b", "ab", "aab", "abab", "aa"]:
    print(f"{w:5} even a's and ends in b: {accepts(w)}")
Open in compiler

Line by line

  1. even_a remembers whether the number of a's is even (E) or odd (O); ends_b remembers whether the last symbol was b (Y) or not (N).
  2. product_dfa builds a move for every pair of states and every symbol, moving both halves at once.
  3. The start pair is (E, N): no a's yet, and the empty string does not end in b.
  4. Only the pair (E, Y) accepts, so the machine accepts strings with an even number of a's that end in b; that is the intersection.
  5. The product has 2 × 2 = 4 states. ab has one a, so it is rejected, while aab and abab have two and end in b.

Expected result

states: 4
b     even a's and ends in b: True
ab    even a's and ends in b: False
aab   even a's and ends in b: True
abab  even a's and ends in b: True
aa    even a's and ends in b: False

In the real world

Product construction is how tools check two rules at once, for example "a valid identifier that is not a keyword". Model checkers verify hardware and protocols by building products of many small state machines. Complement is how a firewall turns "allowed patterns" into "blocked patterns" without writing a second machine by hand.

Common mistakes

  • Complementing an incomplete DFA, so strings that hit a missing move are rejected by both machines.
  • Choosing the wrong accepting pairs: "both accept" is intersection, "either accepts" is union.
  • Forgetting ε when designing: decide whether the start state should accept.
  • Too many states: if two states remember the same thing, merge them.

Best practices

  • Write what each state means as a short comment or name before writing moves.
  • Add a dead state explicitly, rather than leaving moves out.
  • Test a product machine against the two original machines on many short strings.

Summary

Design a DFA by choosing the smallest memory that answers the question. Complement swaps accepting states of a complete DFA. The product construction runs two DFAs together on pairs of states and accepts for intersection or union, which shows that regular languages are closed under these operations.

Quick check

1. To build the complement of a complete DFA, you…
2. Two DFAs have 3 and 4 states. How many states does their product have?
3. In a product DFA for L1 ∪ L2, which pairs accept?
4. Why must a DFA be complete before you swap its accepting states?

Key takeaways

  • Decide what to remember first; the states follow from it.
  • Complement: same machine, swap accepting and non-accepting states (it must be complete).
  • Product: pairs of states; choose the accepting pairs for "and" or for "or".

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.