9
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – vzn
    Dec 2, 2015 at 23:39
  • $\begingroup$ @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. $\endgroup$
    – templatetypedef
    Dec 3, 2015 at 1:04
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Dec 3, 2015 at 2:07

2 Answers 2

Reset to default
7
$\begingroup$

The answer to your question is yes.

See Bonchi, Bonsangue, Rutten and Silva's papers Brzozowski's algorithm (co)algebraically (shorter conference version) and Algebra-Coalgebra Duality in Brzozowski’s Minimization Algorithm (longer journal version with more generalizations).

They give a (lightly) categorical presentation of Brzowzowski's algorithm, and use it to derive versions of it for more general classes of automata, including Moore automata (which gives an affirmative answer to your question).

Improve this answer
$\endgroup$
6
$\begingroup$

Just to add to Neel's answer, in my book Automatic Sequences with Jean-Paul Allouche we discuss DFAO's (deterministic finite automata with outputs), which are exactly what you asked about (associate an output with each state). And Theorem 4.3.3 describes how to reverse such a machine.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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