Skip to content
Tutorials Center
My learning

Topics

Lesson 51 of 59 ยท Projects

Project: A DFA Simulator and Minimizer

Build a complete finite automata toolkit in Python: a DFA simulator, union and complement, the subset construction from NFA to DFA, and a DFA minimizer you can test.

Time to turn theory into code. In this project you will build a small but complete toolkit for finite automata, using nothing but the Python standard library. You will implement exactly the algorithms from the finite-automata chapters: running a DFA, combining DFAs with the product construction, converting an NFA to a DFA with the subset construction, and minimizing a DFA by partition refinement.

Writing these algorithms yourself is the best way to make the theory stick. You will also learn how to test an automaton library: compare against a brute-force check on every short string, so a bug cannot hide.

The plan

flowchart LR
    SPEC["Spec: states,<br/>alphabet, ฮด, start, accepts"] --> DFA["DFA simulator"]
    DFA --> OPS["complement, union,<br/>intersection (product)"]
    NFA["NFA with ฮต-moves"] --> SUB["Subset construction"]
    SUB --> DFA
    OPS --> MIN["Minimizer<br/>(partition refinement)"]
    SUB --> MIN
    MIN --> TEST["Equivalence test<br/>on all short strings"]

The toolkit. Every box is a function you will write in this lesson.

Step 1: a DFA class with complement and product

A DFA has five parts: states, alphabet, transition function, start state and accepting states. We store the transition function as a Python dictionary from (state, symbol) to a state. To keep life simple we require a total function, so there is a transition for every pair. Running the DFA is a single loop.

Two operations come almost for free:

  • Complement: swap accepting and non-accepting states (valid only for a total DFA).
  • Product construction: run two DFAs side by side. A state of the product is a pair (p, q); on symbol a it moves to (ฮด1(p, a), ฮด2(q, a)). Choose the accepting pairs by rule: both accepting gives the intersection, either gives the union.
Python DFA class, complement and product construction

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 that union, intersection and complement of DFAs give DFAs again. This is the programmer's view of the closure properties of regular languages.

Step 2: NFA to DFA with the subset construction

An NFA may have several choices per symbol and may use ฮต-moves. The subset construction builds a DFA whose states are sets of NFA states: the set of states the NFA could be in after reading the input so far. Two helper ideas:

  • ฮต-closure(S): all states reachable from S using only ฮต-moves.
  • move(S, a): all states reachable from S by one transition on symbol a.

The DFA's start state is ฮต-closure({q0}). From a subset S on symbol a, go to ฮต-closure(move(S, a)). A subset is accepting if it contains an NFA accepting state. We build only the subsets that are reachable, so we usually avoid the worst-case 2^n blow-up.

Python Subset construction with epsilon moves

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.

The language "the 3rd symbol from the end is a" needs 2^3 = 8 DFA states, even though the NFA needs only 4: a concrete demonstration that the exponential blow-up of the subset construction cannot be avoided in general.

Step 3: minimizing a DFA

Two states are equivalent if no string distinguishes them (from both, the same strings lead to acceptance). A minimal DFA merges all equivalent states. The standard algorithm is partition refinement (Moore's algorithm):

  1. Remove states unreachable from the start state.
  2. Start with two groups: accepting and non-accepting states.
  3. Split a group whenever two of its states go to different groups on some symbol.
  4. Repeat until no group splits; each remaining group becomes one state of the minimal DFA.
Python DFA minimization by partition refinement

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.

The 6-state machine collapses to 3 states (no 0 seen yet, a 0 just seen, and "found 01"). By the Myhill-Nerode theorem, the minimal DFA is unique up to renaming states, so the number you get is a property of the language itself.

Testing the toolkit

How do you know your code is right? Three habits:

  • Brute-force oracle. For short strings, enumerate all strings up to length 8 to 10 and compare with an independent implementation (as done above).
  • Properties. Complementing twice returns the original language; minimizing twice gives the same size; L โˆฉ complement(L) accepts nothing.
  • Known small answers. The 3rd-from-last language needs exactly 8 states in a minimal DFA, so check that.

Extension ideas

  • Add a DFA equivalence test: two DFAs are equivalent if the product accepts no string in the symmetric difference. Search the product for a reachable accepting pair.
  • Render the automaton as a Graphviz or Mermaid description from the delta table.
  • Convert a regular expression to an NFA (the next project does exactly that).
  • Add the emptiness test (is any accepting state reachable?) and shortest accepted word (breadth-first search).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the product construction for the intersection of two DFAs, which pairs are accepting?

    Intersection requires both machines to accept; for the union you would accept when either does.
  2. 2. Why must the DFA be total before you complement it by swapping accepting states?

    A string that falls off the machine is rejected; after swapping it would still be rejected, but it should now be accepted. A dead state makes the DFA total.
  3. 3. What are the states of the DFA built by the subset construction?

    Each DFA state is the set of NFA states the NFA could be in after reading the same input.
  4. 4. Partition refinement stops when

    When every state in a group sends each symbol to the same group, the remaining groups are the equivalence classes.

Summary

  • A DFA is five parts plus a loop; complement swaps accepting states and the product construction gives union and intersection.
  • The subset construction turns an NFA with ฮต-moves into a DFA whose states are sets of NFA states.
  • Partition refinement minimizes a DFA; the minimal DFA is unique (Myhill-Nerode).
  • Test automata code against brute-force enumeration of short strings and simple algebraic properties.

Next: Project: A Regular Expression Engine