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 we give a few definitions on states .
- is accessible from state p if such that .
- is accessible if it is accessible from .
- is accessible if every state in is accessible.
Every DFA has an equivalent accessible automaton that can be easily computed: simply delete non-accessible states.2
Next, let’s define the machine .
Definition. Given a DFA construct where for all and for all , define . In other words, swap initial and final states and reverse the direction of the arrows. A few things to notice:
- recognizes .
- is definitely not a DFA and is technically not even an NFA because now we have a set of initial states instead of a single initial state. This does not affect much since we can still determinize normally by starting with the entire set of initial states.
Given these definitions, we will prove the crucial lemma needed for Brzozowski’s algorithm.
Lemma. Let be an accessible DFA and be the result of determinizing . is minimal.3
Proof. Let and . To show is minimal, by the Myhill-Nerode theorem, it suffices to show all states in are distinguishable. Let where and represent states of . We show that if and are indistinguishable, then .
Let . Since every state of is accessible, such that . Hence, in . Thus, in .
If and are indistinguishable, then in . Thus, such that in . Hence, . But then , since is deterministic. Thus, .
We have shown and, by symmetry, . Hence, .4 □
Finally, we show the theorem.
Theorem (Brzozowski). Let be an accessible DFA recognizing L. is the minimal automaton recognizing L.5
Proof. By the lemma, is the minimal DFA recognizing . Since it is minimal is must be accessible. By the same lemma, is the minimal DFA recognizing . □