# 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,\Sigma ,\delta ,{q}_{0},F)$ we give a few definitions on states $q,p\in Q$.

- $q$ is
*accessible from state p*if $\exists w\in {\Sigma}^{\ast}$ such that $\delta (p,w)=q$. - $q$ is
*accessible*if it is accessible from ${q}_{0}$. - $M$ is
*accessible*if every state in $M$ 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 ${M}^{R}$.

Definition. Given a DFA $M=(Q,\Sigma ,\delta ,{q}_{0},F)$ construct ${M}^{R}=(Q,\Sigma ,{\delta}^{R},F,\left\{{q}_{0}\right\})$ where for all $a\in \Sigma $ and for all $q\prime \in Q$, define ${\delta}^{R}(q\prime ,a)=\{q\in Q|\delta (q,a)=q\prime \}$. In other words, swap initial and final states and reverse the direction of the arrows. A few things to notice:

- ${M}^{R}$ recognizes ${L}^{R}$.
- ${M}^{R}$ 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 ${M}^{R}$ 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 $M$ be an accessible DFA and ${M}^{~}$ be the result of determinizing ${M}^{R}$. ${M}^{~}$ is minimal.^{3}

Proof. Let ${M}^{R}=(Q,\Sigma ,{\delta}^{R},F,\left\{{q}_{0}\right\})$ and ${M}^{~}=({Q}^{~},\Sigma ,{\delta}^{~},{q}_{0}^{~},{F}^{~})$. To show ${M}^{~}$ is minimal, by the Myhill-Nerode theorem, it suffices to show all states in ${M}^{~}$ are distinguishable. Let $A,B\in {Q}^{~}$ where $A$ and $B$ represent states of $M$. We show that if $A$ and $B$ are indistinguishable, then $A=B$.

Let $p\in A$. Since every state of $M$ is accessible, $\exists w\in {\Sigma}^{\ast}$ such that $\delta ({q}_{0},w)=p$. Hence, ${q}_{0}\in {\delta}^{R}(p,{w}^{R})$ in ${M}^{R}$. Thus, ${\delta}^{~}(A,{w}^{R})\in {F}^{~}$ in ${M}^{~}$.

If $A$ and $B$ are indistinguishable, then ${\delta}^{~}(B,{w}^{R})\in {F}^{~}$ in ${M}^{~}$. Thus, $\exists p\prime \in B$ such that ${q}_{0}\in {\delta}^{R}(p\prime ,{w}^{R})$ in ${M}^{R}$. Hence, $\delta ({q}_{0},w)=p\prime $. But then $p=p\prime $, since $M$ is deterministic. Thus, $p\in B$.

We have shown $A\subseteq B$ and, by symmetry, $B\subseteq A$. Hence, $A=B$.^{4} □

Finally, we show the theorem.

Theorem (Brzozowski). Let $M$ be an accessible DFA recognizing L. ${\left({M}^{~}\right)}^{~}$ is the minimal automaton recognizing L.^{5}

Proof. By the lemma, ${M}^{~}$ is the minimal DFA recognizing ${L}^{R}$. Since it is minimal is must be accessible. By the same lemma, ${\left({M}^{~}\right)}^{~}$ is the minimal DFA recognizing ${\left({L}^{R}\right)}^{R}=L$. □