Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 59 ยท Finite Automata

Designing DFAs: Common Patterns

Learn proven DFA design patterns: counting modulo k, substrings, the k-th symbol from the right, combined conditions and divisibility, each tested in Python.

Designing a DFA is a puzzle with a small number of recurring solutions. Once you can recognize the pattern behind a language, you can write its DFA almost mechanically. This lesson collects the most useful patterns, shows a method for checking your design against a plain Python function, and works through the classic exam examples.

Pattern 1: remember a counter, capped or modulo

If the condition depends on how many times something happened, store that count in the state.

  • "Even number of a's": count modulo 2. States: even, odd.
  • "At least two 0's": count capped at 2. States: 0, 1, "2 or more".
  • "Number of a's divisible by 3": count modulo 3.

Counting modulo k needs k states, and counting at least k needs k+1 states (0, 1, ..., k-1, and "k or more"). A capped counter never needs more than the cap, because after reaching "at least k" nothing else can change the answer.

Pattern 2: combine conditions with a product of states

When a language demands two independent conditions, track both at once. The state becomes a pair, and the number of states is the product. "At least two 0's and at least two 1's" needs a pair (zeros capped at 2, ones capped at 2): 3 ร— 3 = 9 states. "Odd number of 0's or even number of 1's" uses the pair (zeros mod 2, ones mod 2): 4 states, and the accepting states are simply those where the condition holds. The same four-state machine can accept different languages just by changing which states are accepting.

Pattern 3: the shape of the input (phases)

A language like a^n b^m (all a's, then all b's) has phases: the machine is in the "reading a's" phase, then moves to the "reading b's" phase, and any a after a b sends it to a dead state. Combine it with another pattern for extra conditions. For a^n b^m where n + m is even, add the parity of the length to each phase, giving four live states and one dead state.

Pattern 4: look at the last k symbols

Conditions about the end of the string ("ends with 01", "second symbol from the right is a") need the state to remember the last few symbols. Remembering the last k symbols costs at most |ฮฃ|^k states, which is why "the k-th symbol from the right is a" needs 2^k states over {a, b}. In fact this family is the standard proof that nondeterminism can make machines exponentially smaller, as you will see in NFA to DFA conversion.

Pattern 5: arithmetic on the string's value

For binary numbers read most significant bit first, the value after reading bit b from value v is 2v + b. To test "divisible by k", keep only v mod k: the new remainder is (2r + b) mod k. This gives exactly k states. Divisible by 3 needs three states, divisible by 5 needs five.

A test harness: derive the DFA by exploration

You do not have to draw the whole table by hand. Write the step rule as a function step(state, symbol), and let a program explore every reachable state to build the table and verify it against a brute-force Python predicate over all short strings.

Python Build DFAs from a step function and verify them

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All four report zero mismatches, and the state counts match the analysis above: 9, 3, 7 and 5. The "second symbol from the right" machine has 7 reachable states here because we stored the raw last-two-symbols string, including the short strings at the start; it can be shrunk to 4 states with minimization, which merges states that behave identically.

Same states, different accepting set

Take the machine tracking (number of 0s mod 2, number of 1s mod 2). Four states, one transition rule, and a whole family of languages differing only in which states accept.

flowchart LR
    s00(("e0,e1")) -->|"0"| s10(("o0,e1"))
    s00 -->|"1"| s01(("e0,o1"))
    s10 -->|"0"| s00
    s10 -->|"1"| s11(("o0,o1"))
    s01 -->|"0"| s11
    s01 -->|"1"| s00
    s11 -->|"0"| s01
    s11 -->|"1"| s10

Each state is labeled with the parity of zeros and ones seen so far. Start state: e0,e1.

Python One machine, many languages

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice how "odd OR even" accepts the largest set: its accepting set has three of the four states. Complement and intersection of such conditions are exactly the DFA operations you will study soon.

Common mistakes

  • Forgetting a transition. In a hand-drawn DFA, verify every state has an arrow for every symbol.
  • Mixing up "at least k" and "exactly k". Exactly k needs a dead state when the count goes above k.
  • Accepting the empty string by accident. Ask whether ฮต belongs to the language and mark the start state accordingly.
  • Too few states. If two different prefixes need different futures (like "ends in 0" versus "ends in 1" for a last-symbol test), they must be different states.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many states does a DFA need to track 'number of 1s is at least 3'?

    States for counts 0, 1, 2 and '3 or more': that is k + 1 = 4 states. The last state is accepting and loops on every symbol.
  2. 2. A DFA tracks the remainder mod 3 of a binary number read MSB first. After remainder r and bit b, what is the new remainder?

    Reading a bit shifts the number left (multiplying by 2) and adds the bit, so the new value is 2v + b, and its remainder is (2r + b) mod 3.
  3. 3. Which language needs a dead state in its DFA?

    If the first symbol is b the string can never be fixed, so the machine needs a trap state. The other languages can recover from any prefix.
  4. 4. What is the minimum number of states for 'the 3rd symbol from the right is a' over {a, b}?

    The machine must remember the last three symbols, which gives 2^3 = 8 distinct situations, and a minimal DFA cannot merge any of them.

Summary

  • Choose the pattern first: modulo counter, capped counter, product of conditions, phases, last-k-symbols or arithmetic remainder.
  • State count is a design measure: k for mod k, k+1 for at least k, products for combined conditions, 2^k for the k-th symbol from the right.
  • Changing only the accepting set of a fixed machine produces different languages.
  • Verify designs by brute-force comparison against a simple Python predicate.

Next: Nondeterministic Finite Automata and ฮต-moves