Introduction

Alright, DFA fans, time to look at the Equivalence Problem. We ask: given two DFAs $D_1$ and $D_2$, do they accept exactly the same language? Spoiler: unlike Turing machines, DFAs are nice enough that this is decidable in polynomial time.

Formal Setup

Let

$$ D_i = (Q_i, Σ, δ_i, q_{0,i}, F_i) \quad\text{for } i=1,2. $$

We want to check whether

$$ L(D_1) = L(D_2). $$

A decider for equivalence would output 1 if they match and 0 otherwise.

Example DFAs

# DFA E1 and E2 both accept strings over {0,1} with an even number of 1's:
# E1: tracks parity in two states q0->q1 on '1', q1->q0 on '1'.
# E2: same idea but reversed transitions.

# DFA E3 accepts strings with an odd number of 1's.

  • Question: Are E1 and E2 equivalent? Answer: Yes, both accept exactly the even-ones strings.

  • Question: Are E1 and E3 equivalent? Answer: No, they differ on any string with even vs. odd count of 1’s.

Algorithm (Using Symmetric Difference)

  1. Build the product automaton for the symmetric difference:

    • States: $Q = Q_1 \times Q_2$.
    • Start: $(q_{0,1}, q_{0,2})$.
    • Accepting: those $(p,q)$ where one is accepting and the other isn’t: $F = (F_1 \times (Q_2 \setminus F_2)) \cup ((Q_1 \setminus F_1) \times F_2)$.
    • Transitions: $δ((p,q), a) = (δ_1(p,a), δ_2(q,a)).$

  2. Check emptiness of this difference automaton using a reachability search (BFS/DFS):

    • If no accepting state is reachable from $(q_{0,1}, q_{0,2})$, then $L(D_1) = L(D_2)$.
    • Otherwise, they differ on at least one string.

This runs in $O(|Q_1|\cdot|Q_2|\cdot|Σ|)$ time.

Why It Matters

  • Compiler Checks: Ensuring two regex-derived DFAs match the same pattern.
  • Minimization: Equivalence checking is used in DFA minimization algorithms.

Wrap-Up

DFA equivalence is a breeze: build the symmetric-difference DFA and test emptiness. Next up: the Universality Problem for DFAs, can a DFA accept all strings? Let’s see!