Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 59 ยท Finite Automata

Minimization of DFAs

Learn how to minimize a DFA by removing unreachable states and merging equivalent states, using partition refinement and the table-filling method, with Python code.

Two DFAs can accept exactly the same language while having very different sizes. Designs built from mechanical constructions, such as the product construction or the subset construction, often contain redundant states. DFA minimization produces the smallest DFA for a language, and, remarkably, that smallest DFA is unique (up to renaming the states). This is useful for smaller code, faster execution, and, as you will see, for a simple test of whether two machines are equivalent.

Step 1: remove unreachable states

A state that cannot be reached from the start state by any input string can never influence the result. Find all reachable states with a graph search from q0 and delete the rest. This step comes first because unreachable states can confuse the merging step.

Step 2: merge equivalent states

Two states p and q are equivalent if, for every string w, reading w from p ends in an accepting state exactly when reading w from q does. Equivalent states have the same "future", so they can be merged into one without changing the language.

You never need to test all strings. Instead, look for distinguishing strings by working outward:

  • If exactly one of p, q is accepting, they are distinguished by the empty string ฮต.
  • If for some symbol a the successors ฮด(p, a) and ฮด(q, a) are already distinguished, then p and q are distinguished too (by a followed by the distinguishing string).

Partition refinement (Moore's algorithm)

  1. Start with two groups: accepting states and non-accepting states.
  2. Repeat: split any group in which two states move into different groups on some symbol.
  3. Stop when no group can be split. Each remaining group is one state of the minimal DFA.

The table-filling method

An equivalent hand method: make a triangle table of all state pairs. Mark every pair where one state accepts and the other does not. Then repeatedly mark a pair (p, q) if for some symbol a the pair (ฮด(p, a), ฮด(q, a)) is already marked. When nothing changes, the unmarked pairs are equivalent states.

A worked example

Here is a DFA that counts the number of a's modulo 4 and accepts when the count is even (c0 and c2 accept). Both c0 and c2 behave identically, and so do c1 and c3. The minimal machine has two states. It also has an unreachable state x that we remove first.

flowchart LR
    start(( )) --> c0
    c0((("c0"))) -->|"a"| c1(("c1"))
    c1 -->|"a"| c2((("c2")))
    c2 -->|"a"| c3(("c3"))
    c3 -->|"a"| c0
    c0 -->|"b"| c0
    c1 -->|"b"| c1
    c2 -->|"b"| c2
    c3 -->|"b"| c3

Counting a's mod 4 with accepting set {c0, c2}. Merge c0 with c2, and c1 with c3: two states, "even" and "odd".

Refinement trace: start with groups {c0, c2} (accepting) and {c1, c3, x}... after removing x, {c1, c3}. On a, c0 goes to c1 and c2 goes to c3, which are in the same group, so no split. On b each loops to itself, same group. Nothing splits, so the partition {c0, c2}, {c1, c3} is final.

Implementing Moore's algorithm

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 output shows two classes, ['c0', 'c2'] and ['c1', 'c3'], with x gone. The new transition table has two states: a flips between them and b loops.

Shrinking an automatically generated DFA

Mechanical constructions can bloat a machine. Earlier, we built a DFA for "the second symbol from the right is a" by remembering the last two symbols, which produced 7 states. The minimal DFA has 4. The code below builds the 7-state machine, then minimizes it and checks that the language is unchanged.

Python Minimize a machine and confirm the language

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 classes are {ฮต, b, bb}, {a, ba}, and . The start state (nothing read) merges with b and bb, because none of them has an a in the second-to-last position yet, and a merges with ba because both have only a single a as the last symbol. Four is the minimum: each class can lead to a different future, so no further merging is possible.

Uniqueness and equivalence testing

The minimal DFA for a regular language is unique up to renaming of states. This gives an algorithm to test whether two DFAs accept the same language: minimize both and compare the results. Another approach is to build the product DFA for the symmetric difference L1 ฮ” L2 and check that it has no reachable accepting state. Equivalence of regular languages is therefore decidable, in sharp contrast with context-free languages, where the same question has no algorithm.

The Myhill-Nerode theorem explains why the minimal DFA is unique and why its size equals the number of distinguishable prefix classes of the language, which also gives a tool to prove that some languages are not regular.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the first step of DFA minimization?

    Unreachable states never affect the language and can confuse the merging step, so they are deleted first.
  2. 2. When are two states p and q distinguishable?

    States are equivalent only if every string behaves identically from both. A single string that gives different outcomes distinguishes them.
  3. 3. In partition refinement, what is the initial partition?

    States where acceptance differs are already distinguished by ฮต, so we start with the two groups and split further.
  4. 4. A DFA with 12 states minimizes to 5 states. What can you conclude?

    The minimal DFA is unique and has the smallest possible number of states, so no DFA with fewer than 5 states can recognize the language.
  5. 5. How can two DFAs be tested for language equivalence?

    Minimal DFAs are unique up to renaming, so equal languages give isomorphic minimal machines.

Summary

  • Minimization removes unreachable states and merges equivalent ones; the result is the unique smallest DFA.
  • Moore's partition refinement starts with {accepting, non-accepting} and splits groups until stable; table filling marks distinguishable pairs.
  • Minimization shrinks machines from the subset or product constructions and decides language equivalence.
  • Minimal size is tied to the number of distinguishable prefix classes, the idea behind the Myhill-Nerode theorem.

Next: Mealy and Moore Machines