[Solved]: Problem with implementing Brzozowski’s algorithm

ignougroup
Problem Detail: I’ve been trying to implement Brzozowski’s algorithm but I’ve just discovered that it creates suboptimal automata for a certain class of inputs, having one more state than what is really needed in the result. I can show it on a trivial automaton:

   a b           a   b           a b            a     b            a b >0 0 1  rev  *0 0,2  -   det  >0 - 1  rev  *0   -     -    det  >0 1 2  1 1 2  -->   1  1   0   -->   1 2 5  -->   1   -    0,4   -->   1 1 2 *2 0 2       >2  -  1,2        2 2 3        2  1,2    -          2 2 3                               *3 4 -        3   -     2         *3 1 3                               *4 4 1        4  3,4    -                                         *5 5 5        5   5    1,5                                                     >6 3,4,5 1,2,5

Here rev is the edge reversal part, where I’d already removed the transitions on epsilon, and det is determinization through powerset construction, creating new states as soon as it discovers them, recursively. The problem here is this: once I add the extra state to make up for the three different start states after the first edge reversal and powerset construction, nothing ever returns to that state and thus I can’t get rid of it later for being equivalent to the original start state. Is there something wrong with the way I’m doing it? Am I missing something?

Asked By : Přemysl J.

Answered By : A.Schulz

This is an excellent question! The reverting step in Brzozowski’s Algorithm does not introduce a new virtual starting state that leads to the old accepting states via $varepsilon$-transitions. Instead it allows multiple starting states, which is no big problem, if you construct the product-automaton anyway right after the reversion. Conceptually, it is the easiest to consider reverting and determinization as one single step. If your DEA is $M=(Q,Sigma,delta,q_0,F)$, then define as the reverted DEA $ M^R=(Q^R,Sigma,delta^R,q_0^R,F^R)$ as follows:

  • $Q^R=mathcal{P}(Q)$,
  • $q_0^R=F$,
  • $F^R={ Psubseteq Q mid q_0in P}$,
  • $delta^R(P,a):={ pin Q mid delta(p,a)in P}$.

(You might want to ignore states that are not reachable.) Brzozowski’s Theorem states that $(M^R)^R$ is a minimal DEA accepting $L(M)$. For further reading I suggest Elements of Automata Theory by Sakarovitch pages 116-117.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6138  Ask a Question  Download Related Notes/Documents

Leave a Reply