<p>Just to add to Neel's answer, in my book <em>Automatic Sequences</em> 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.</p>

CC BY-SA 3.0
2015-12-03T11:54:28.520Z
2015-12-03T11:54:28.520Z
Jeffrey Shallit
<p>The answer to your question is yes.</p>

<p>See Bonchi, Bonsangue, Rutten and Silva's papers <a href="http://homepages.cwi.nl/~janr/papers/files-of-papers/2011_SEN1114.pdf"><em>Brzozowski's algorithm (co)algebraically</em></a> (shorter conference version) and <a href="http://www.cs.mcgill.ca/~prakash/Pubs/BrzMin.pdf"><em>Algebra-Coalgebra Duality in Brzozowski’s Minimization Algorithm</em></a> (longer journal version with more generalizations). </p>

<p>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). </p>

CC BY-SA 3.0
2015-12-03T11:26:21.907Z
2015-12-03T11:26:21.907Z
Neel Krishnaswami
<p>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$.</p>

<p>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.</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2015-12-02T23:39:02.057Z
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
CC BY-SA 3.0
2015-12-03T01:04:18.987Z
@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.
templatetypedef
CC BY-SA 3.0
2015-12-03T02:07:18.740Z
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](http://cstheory.stackexchange.com/questions/18915/how-to-minimize-a-fsm-transducer) that is apparently not ("yet"?) fully tied in with DFA minimizing.
vzn
<automata-theory><minimization>
Generalizing Brzozowski's DFA minimization algorithm to finite automata with different classes of accepting states?
templatetypedef
# Generalizing Brzozowski's DFA minimization algorithm to finite automata with different classes of accepting states?

(Asked by: username_0 on 2015-12-02)

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?

**Tags:** automata-theory, minimization

> **Comments:**
> **username_1**: 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  
> **username_0**: @username_1 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.  
> **username_1**: 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](http://cstheory.stackexchange.com/questions/18915/how-to-minimize-a-fsm-transducer) that is apparently not ("yet"?) fully tied in with DFA minimizing.  

---

## 2 answers

### Answer by username_3 on 2015-12-03. Score: 7 | Accepted answer

The answer to your question is yes.

See Bonchi, Bonsangue, Rutten and Silva's papers [*Brzozowski's algorithm (co)algebraically*](http://homepages.cwi.nl/~janr/papers/files-of-papers/2011_SEN1114.pdf) (shorter conference version) and [*Algebra-Coalgebra Duality in Brzozowski’s Minimization Algorithm*](http://www.cs.mcgill.ca/~prakash/Pubs/BrzMin.pdf) (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).


---

### Answer by username_2 on 2015-12-03. Score: 6

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.


---

