# Generalizing Brzozowski's DFA minimization algorithm to finite automata with different classes of accepting states?

Brzozowski's algorithm for converting a DFA into an equivalent minimum-state DFA is remarkably simple: if $R(D)$ denotes the NFA formed by reversing all the edges in a DFA $D$, making the old start state an accepting state, and making the old accepting states start states, and if $P(N)$ denotes the result of applying the subset construction to the NFA $N$, then $$P(R(P(R(D))))$$ is a minimum-state DFA with the same language as $D$.

We can think of a DFA as a computational device that accepts an input string $w$ and then outputs 0 if $w$ ends in a rejecting state and 1 if $w$ ends in an accepting state. A natural generalization of DFAs associated each state in the DFA with some natural number between 0 and $k-1$, inclusive.

To the best of my knowledge, it's possible to minimize these modified classes of DFAs by using a distinguishability-based minimization algorithm, such as the canonical one by Hopcroft. However, I can't see how it would be possible to adapt Brzozowski's minimization algorithm to this new class of automata because the key step (reversing the automaton) no longer has a clear interpretation in this generalized setting.

Is there a known generalization of Brzozowski's algorithm for minimizing these sorts of automata? If not, are there any theoretical reasons why we'd expect that such a modified algorithm wouldn't exist?

• the "generalization" does not seem to be clearly defined. what is $k$? is it just talking about associating each state in a DFA with a bounded integer value? then what? what is an example? who works with this? etc
– vzn
Dec 2, 2015 at 23:39
• @vzn You can think of each state in a normal DFA as being associated with either 0 or 1 (reject and accept states, respectively). I'm thinking about generalizing this to the case where each DFA state is associated with some value in $\{0, 1, 2, 3, ..., k-1\}$, and the DFA outputs the number associated with the state that the string ends up in. Dec 3, 2015 at 1:04
• ok, thats not communicated in the post at all, "the DFA outputs the # associated with the state the string ends in", suggest you fix that. also, DFAs technically have no "output". maybe you mean FSM transducer? there is indeed some partial theory associated with FSM transducer minimization that is apparently not ("yet"?) fully tied in with DFA minimizing.
– vzn
Dec 3, 2015 at 2:07