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)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)}")Line by line
even_aremembers whether the number of a's is even (E) or odd (O);ends_bremembers whether the last symbol was b (Y) or not (N).product_dfabuilds a move for every pair of states and every symbol, moving both halves at once.- The start pair is (E, N): no a's yet, and the empty string does not end in b.
- 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.
- The product has 2 × 2 = 4 states.
abhas one a, so it is rejected, whileaabandababhave 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
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.