7
$\begingroup$

Brzozowki's algorithm is cited widely. Several questions here give examples or discuss its complexity. But I haven't been able to find a proof of correctness for the algorithm. How do we prove it correct? Any proof accessible to CS undergraduates would be very welcome.

$\endgroup$
  • 3
    $\begingroup$ Prove it? I can't even spell it. $\endgroup$ – David Richerby Mar 14 at 18:53
9
$\begingroup$

The proof of Brzozowski's result is technical, but not very complicated. In fact we only have to consider one sequence of reversal-determinization, to obtain the minimality result we want. (The first sequence of reversal determination leads to a deterministic FSA for the reversal of the original language; the minimality proof is for the second reversal-determinization.)

First one needs some good view of the different automata involved. And nerves of steel.

The construction of Brzozowski. Let $A = (Q, \Sigma, \delta, q_0, F)$ be a deterministic automaton for the language $L=L(A)$. We assume that all states of $Q$ are reachable from the initial state $q_0$.

In the first step one reverses the automaton: all edges are inverted, and inital and final states are swapped. Informally we get the automaton $\mathrm{rev}(A) = (Q, \Sigma, \delta^{-1}, F, q_0)$.

In the second step one determinizes the automaton so obtained, by the standard construction, but keeping only reachable states. We get $A'= \mathrm{det}(\mathrm{rev}(A)) = (Q', \Sigma, \delta', q'_0, F')$. The states of $A'$ are sets of states for $\mathrm{rev}(A)$: $Q'\subseteq 2^Q$; the initial state consists of the initial states for $\mathrm{rev}(A)$, which are final states in $Q$: $q'_0 = F$; the final states in $A'$ are the states that contain a final state for $\mathrm{rev}(A)$: $U\in F'$ iff $q_0\in U$.

The key of the proof is the following important relation between automata $A$ and $A'$.

enter image description here

Basic Observation: $q\in \delta'(X,w^R)$ iff $\delta(q,w) \in X$.

Proof (one side only). $q\in \delta'(X,w^R)$ iff there exists a state $p$ in $X$ and a path from $p$ to $q$ in $\mathrm{rev}(A)$ with label $w^R$. But that means there is a path from $q$ to $p$ with label $w$ in $A$, or $\delta(q,w) = p$; thus $\delta(q,w) \in X$. end-of-proof.

As announced, this is used to prove the essential property we need.

Property: $A'$ is minimal (and deterministic for $L^R$).

Proof. Let $U$ and $V$ be two states in $A'$ that cannot be distinguished. This means that for any string $w^R$ we have $\delta'(U,w^R) \in F'$ iff $\delta'(V,w^R) \in F'$. We show that now $U$ and $V$ are equal.

By the construction of $F'$ we can rephrase indistinguishability as $\delta'(U,w^R) \ni q_0$ iff $\delta'(V,w^R) \ni q_0$.

Apply the Basic Observation, and we have $\delta(q_0,w) \in U$ iff $\delta(q_0,w) \in V$.

From this equality $U=V$ follows, as all states in $Q$ are assumed to be reachable, thus for any state $p$ in $U$ or $V$ there is a string $w$ such that $p = \delta(q_0,w)$. end-of-proof.

But even after proving, the result is still real magic!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.