# 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=\left(Q,\Sigma ,\delta ,{q}_{0},F\right)$ 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 \left(p,w\right)=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=\left(Q,\Sigma ,\delta ,{q}_{0},F\right)$ construct ${M}^{R}=\left(Q,\Sigma ,{\delta }^{R},F,\left\{{q}_{0}\right\}\right)$ where for all $a\in \Sigma$ and for all $q\prime \in Q$, define ${\delta }^{R}\left(q\prime ,a\right)=\left\{q\in Q|\delta \left(q,a\right)=q\prime \right\}$. 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}=\left(Q,\Sigma ,{\delta }^{R},F,\left\{{q}_{0}\right\}\right)$ and ${M}^{~}=\left({Q}^{~},\Sigma ,{\delta }^{~},{q}_{0}^{~},{F}^{~}\right)$. 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 \left({q}_{0},w\right)=p$. Hence, ${q}_{0}\in {\delta }^{R}\left(p,{w}^{R}\right)$ in ${M}^{R}$. Thus, ${\delta }^{~}\left(A,{w}^{R}\right)\in {F}^{~}$ in ${M}^{~}$.

If $A$ and $B$ are indistinguishable, then ${\delta }^{~}\left(B,{w}^{R}\right)\in {F}^{~}$ in ${M}^{~}$. Thus, $\exists p\prime \in B$ such that ${q}_{0}\in {\delta }^{R}\left(p\prime ,{w}^{R}\right)$ in ${M}^{R}$. Hence, $\delta \left({q}_{0},w\right)=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$.