Brzozowski’s Algorithm

I first came across Brzozowski’s algorithm as an aside in a book on the theory of computation.1 I found the proposition incredibly surprising, but couldn’t find an decent proof online. Below is a slightly adapted proof with some additional commentary.

First, let’s define an accessible automaton.

Definition. Given a DFA M=(Q,Σ,δ,q0,F) we give a few definitions on states q,pQ.

Every DFA has an equivalent accessible automaton that can be easily computed: simply delete non-accessible states.2

Next, let’s define the machine MR.

Definition. Given a DFA M=(Q,Σ,δ,q0,F) construct MR=(Q,Σ,δR,F,{q0}) where for all aΣ and for all qQ, define δR(q,a)={qQ|δ(q,a)=q}. In other words, swap initial and final states and reverse the direction of the arrows. A few things to notice:

Given these definitions, we will prove the crucial lemma needed for Brzozowski’s algorithm.

Lemma. Let M be an accessible DFA and M~ be the result of determinizing MR. M~ is minimal.3

Proof. Let MR=(Q,Σ,δR,F,{q0}) and M~=(Q~,Σ,δ~,q0~,F~). To show M~ is minimal, by the Myhill-Nerode theorem, it suffices to show all states in M~ are distinguishable. Let A,BQ~ where A and B represent states of M. We show that if A and B are indistinguishable, then A=B.

Let pA. Since every state of M is accessible, wΣ such that δ(q0,w)=p. Hence, q0δR(p,wR) in MR. Thus, δ~(A,wR)F~ in M~.

If A and B are indistinguishable, then δ~(B,wR)F~ in M~. Thus, pB such that q0δR(p,wR) in MR. Hence, δ(q0,w)=p. But then p=p, since M is deterministic. Thus, pB.

We have shown AB and, by symmetry, BA. Hence, A=B.4

Finally, we show the theorem.

Theorem (Brzozowski). Let M be an accessible DFA recognizing L. (M~)~ is the minimal automaton recognizing L.5

Proof. By the lemma, M~ is the minimal DFA recognizing LR. Since it is minimal is must be accessible. By the same lemma, (M~)~ is the minimal DFA recognizing (LR)R=L.