Transducers are machines which do not only have input, but output as well. One can imagine them as automata with two tapes: an input and an output tape. In this book, we consider only the simplest transducers: they are finite and they give an output letter as a response to every input letter. In this section, we briefly describe two types of finite state transducers.

We start by giving the formal definition of Mealy automata.

**Definition 17.**
*A Mealy automaton is an ordered sextuple A = (Q, T, V, q*_{0}, *δ, μ*),
*where Q, T, q*_{0}, *δ are the
same as at the completely defined deterministic finite state acceptors, i.e., Q is the finite set
of states, T is the input alphabet, q*_{0} *∈ Q is the initial state, δ : Q × T → Q is
the transition function; and V is the output alphabet and μ : Q × T → V is the output
function.*

Notice that there are no final (or accepting) states. These automata are not used to accept languages.

A Mealy automaton can be defined by a Cayley table or by a graph. When a Cayley table is used to
describe a Mealy automaton,
then both the values *δ*(*q,a*) and *μ*(*q,a*),
as pairs are written to the cell identified by
the state *q* and by the letter *a*.
When a graph is used to describe a Mealy automaton, then we can put *a/x* to an arrow meaning that
the transition represented by the arrow is performed by reading an input letter *a*, while an
output letter *x* ∈ *V* is written to the output tape.
Here is an example.

**Example 30.** *Let the Mealy automaton A be given by the following Cayley table*

T Q | →q_{1} | q_{2} | q_{3} | q_{4} |
---|---|---|---|---|

a | (q_{4}, x) | (q_{3}, y) | (q_{1}, y) | (q_{2}, x) |

a | (q_{1}, y) | (q_{1}, x) | (q_{2}, x) | (q_{2}, y) |

a | (q_{1}, x) | (q_{1}, x) | (q_{4}, y) | (q_{3}, y) |

*The same automaton given by graph can be seen in Figure 2.11.*

*Let us make some sample runs of the automaton:*

*Let the input be abcabc, then the output is xyxxyx.**Let the input be aaaabbbb, then the output is xxyyyyyy.**Let the input be ccabcabc, then the output is xxxyxxyx.**Let the input be abcbbccabac, then the output is xyxyyxxxyyy.*

**Example 31.** *Animation 6. shows an example of a Mealy automaton,
how it produces output for a given input.*

We say that two Mealy automata are equivalent if they assign the same output word for every input
word *u* ∈ *T*^{*}. The number of states of equivalent automata can be various.
However, there is particular Mealy automaton for each equivalent class that has a minimal number of states. This
automaton can be obtained from any automaton of the class by the minimization algorithm.

Now we present the minimization algorithm for Mealy automata. First, as with the finite state recognizers, we should check which states can be reached from the initial state. The states that cannot be reached can simply be erased from the automaton (table or graph) together with the transitions from them.

When we have a Mealy automaton, such that each of its states is reachable from the initial state with some input words (i.e., reading the given input word the automaton arrives to this particular state), then we can start an analogous algorithm that was used for minimizing finite state recognizers.

Only the initial step of the algorithm differs from the one shown previously: since we have no
accepting states, the initial classification is done in another way. Let two states p and q be
in the same class, i.e., *C*_{1}[*p*] = *C*_{1}[*q*]
if and only if for every input letter *a* ∈ *T* the
equality *μ*(*p,a*) = *μ*(*q,a*) is fulfilled.

The other steps of the algorithm are similar to the previously described algorithm: based on the previous classification the next classification is obtained by separating those states for which there is an input letter such that the transition function with this letter brings them to different classes.

Let us see an example.

**Example 32.** *Let the Mealy automaton A be given as follows:*

T Q | →q_{1} | q_{2} | q_{3} | q_{4} | q_{5} | q_{6} |
---|---|---|---|---|---|---|

a | (q_{2}, x) | (q_{1}, z) | (q_{6}, x) | (q_{5}, z) | (q_{4}, x) | (q_{5}, x) |

b | (q_{3}, y) | (q_{2}, y) | (q_{4}, y) | (q_{4}, y) | (q_{3}, y) | (q_{2}, y) |

*Give the minimal Mealy automaton that is equivalent to A.*

*Solution:*

*One can easily check that every state can be reached from the initial state. Then classification
C*_{1} = {*Q*_{1}, *Q*_{2}}, *where
Q*_{1} = {*q*_{1}, *q*_{3},
*q*_{5}, *q*_{6}} *(having output x for input a and
output y for input b) and Q*_{2} = {*q*_{2}, *q*_{4}}
*(having output z for input a and output y for input b). Then, the transition function
reflecting this classification is as follows:*

Q | Q_{1} | Q_{2} | |||||
---|---|---|---|---|---|---|---|

T | →q_{1} | q_{3} | q_{5} | q_{6} | q_{2} | q_{4} | |

a | Q_{2} | Q_{1} | Q_{2} | Q_{1} | Q_{1} | Q_{1} | |

b | Q_{1} | Q_{2} | Q_{1} | Q_{2} | Q_{2} | Q_{2} |

*Then, Q*_{1} *is divided into two subgroups in the classification
C*_{2} = {*Q*_{11}, *Q*_{12},
*Q*_{2}} *with Q*_{11} =
{*q*_{1}, *q*_{5}} *and
Q*_{12} = {*q*_{3}, *q*_{6}}.
*(Q*_{2} = {*q*_{2}, *q*_{4}}
*remains the same group.) The transition function reflecting these groups is as follows:*

Q | Q_{11} | Q_{12} | Q_{2} | ||||
---|---|---|---|---|---|---|---|

T | →q_{1} | q_{5} | q_{3} | q_{6} | q_{2} | q_{4} | |

a | Q_{2} | Q_{2} | Q_{11} | Q_{12} | Q_{11} | Q_{11} | |

b | Q_{12} | Q_{12} | Q_{2} | Q_{2} | Q_{2} | Q_{2} |

*Only Q*_{12} *is divided (to its elements) and thus
C*_{3} = {*Q*_{11}, *Q*_{121},
*Q*_{122}, *Q*_{2}} *with
Q*_{121} = {*q*_{3}} *and
Q*_{122} = {*q*_{5}}. *Then the transitions become:*

Q | Q_{11} | Q_{121} | Q_{122} | Q_{2} | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|

T | →q_{1} | q_{5} | q_{3} | q_{6} | q_{2} | q_{4} | ||||||

a | Q_{2} | Q_{2} | Q_{11} | Q_{122} | Q_{11} | Q_{11} | ||||||

b | Q_{121} | Q_{121} | Q_{2} | Q_{2} | Q_{2} | Q_{2} |

*Since C*_{4} = *C*_{3}, *we can give the minimal Mealy
automaton (writing also the values of the output
function into the table):*

T Q | →Q_{11} | Q_{121} | Q_{122} | Q_{2} |
---|---|---|---|---|

a | (Q_{2}, x) | (Q_{11}, x) | (Q_{122}, x) | (Q_{11}, z) |

b | (Q_{121}, y) | (Q_{2}, x) | (Q_{2}, y) | (Q_{2}, y) |

**Exercise 41.**
*Let the Mealy automaton A be given with its table as follows:*

T Q | →q_{0} | q_{1} | q_{2} | q_{3} |
---|---|---|---|---|

0 | (q_{0}, a) | (q_{3}, a) | (q_{1}, b) | (q_{2}, b) |

1 | (q_{1}, b) | (q_{1}, a) | (q_{2}, b) | (q_{2}, a) |

*Draw the graph of automaton A.*

**Exercise 42.**
*Let the Mealy automaton A be given by its graph as it is shown in Figure 2.12.*

*Describe the same automaton with a Cayley table.*

*What is the output of this automaton for the input strings aaabb, abbba, bbbaabb and
aabbbaabab?*

*Give a minimal Mealy automaton that is equivalent to A.*

**Exercise 43.** *Give a minimal Mealy automaton that is equivalent to the following one:*

T Q | →q_{1} | q_{2} | q_{3} | q_{4} | q_{5} | q_{6} | q_{7} | q_{8} |
---|---|---|---|---|---|---|---|---|

a | (q_{8}, 0) | (q_{3}, 1) | (q_{8}, 0) | (q_{1}, 1) | (q_{8}, 0) | (q_{4}, 0) | (q_{3}, 1) | (q_{5}, 1) |

b | (q_{2}, 1) | (q_{1}, 0) | (q_{7}, 0) | (q_{2}, 1) | (q_{7}, 1) | (q_{2}, 1) | (q_{6}, 0) | (q_{3}, 1) |

**Exercise 44.** *Give a minimal Mealy automaton that is equivalent to the one defined by the following table.*

T Q | →q_{1} | q_{2} | q_{3} | q_{4} | q_{5} |
---|---|---|---|---|---|

a | (q_{2}, x) | (q_{2}, y) | (q_{2}, x) | (q_{5}, y) | (q_{4}, y) |

b | (q_{4}, x) | (q_{3}, x) | (q_{1}, x) | (q_{3}, x) | (q_{3}, x) |

c | (q_{5}, y) | (q_{5}, x) | (q_{1}, y) | (q_{5}, x) | (q_{2}, x) |

In this subsection another type of finite transducers are investigated.

**Definition 18.**
*A Moore automaton is an ordered sextuple A* = (*Q, T, V, q*_{0}, *δ, η*),
*where Q, T, V, q*_{0}, *δ are
the same as at the Mealy automata, and η : Q* × *V is the output function.*

Notice that the difference between the Mealy and the Moore automata is due to their output function. While with the Mealy automata the output is produced during the transition (depending on both the state that the automaton was in and on the read input letter), at the Moore automata the output letter is produced after the transition is finished and the output letter depends only on the state the automaton reached by the transition.

The Moore automata can also be defined by Cayley table and by graph. Since with the Moore automata the output depends only on the state the automaton has reached, the output letters are written to the states (above the states, when the states are in the 0th row of table) and inside the circles of the states as pairs containing the state and the output assigned to the state on the graphs. Here is an example:

**Example 33.**
*Let the Moore automaton A be given by its graph as it is shown in Figure 2.13.*

*Describe the same automaton using a Cayley table. Give the output for input strings*

*
aabb,
baabaa and
abaababb.
*

*Solution:*

V | 0 | 1 | 0 | 1 |
---|---|---|---|---|

T Q | →q_{0} | q_{1} | q_{2} | q_{3} |

a | q_{2} | q_{3} | q_{0} | q_{3} |

b | q_{1} | q_{2} | q_{3} | q_{2} |

*The example runs give the outputs as follows: *

*For input aabb the output is 0010.**For input baabaa the output is 111000.**For input abaababb the output is 01110010.*

**Example 34.** *Animation 7. shows a Moore automaton at work.*

Now we can generalize the equivalence relation between finite transducers: a Mealy/Moore automaton
*A* is equivalent to a Mealy/Moore automaton *A'* if and only if for every input string
*u* ∈ *T*^{*}
they produce the same output string.

The Moore automata can also be minimized and its algorithm is very similar to the previously
described minimization algorithms.
The only difference is that in this case the first classification is done based on the output
letters assigned to the states, i.e.,
the states *p* and *q* are in the same class by classification *C*_{1} if and only if
*η*(*p*) = *η*(*q*).

Let us see an example of how the algorithm works for the Moore automata.

**Example 35.** *The Moore automata A is defined by its Cayley table as follows:*

V | x | y | y | y | x | x | x |
---|---|---|---|---|---|---|---|

T Q | →q_{1} | q_{2} | q_{3} | q_{4} | q_{5} | q_{6} | q_{7} |

a | q_{2} | q_{5} | q_{1} | q_{5} | q_{2} | q_{3} | q_{4} |

b | q_{7} | q_{4} | q_{6} | q_{2} | q_{4} | q_{6} | q_{1} |

*Find a minimal Moore automaton that is equivalent to A.*

*Solution: *

*First we check if every state is reachable from the initial state. It can be seen that states q*_{3}
*and q*_{6} *are not reachable, therefore we erase them.
We need to minimize the automaton *

V | x | y | y | x | x |
---|---|---|---|---|---|

T Q | →q_{1} | q_{2} | q_{4} | q_{5} | q_{7} |

a | q_{2} | q_{5} | q_{5} | q_{2} | q_{4} |

b | q_{7} | q_{4} | q_{2} | q_{4} | q_{1} |

*Classification C*_{1} =
{*Q*_{1}, *Q*_{2}} *is based on the output function:
Q*_{1} = {*q*_{1}, *q*_{5},
*q*_{7}}
*(having output x) and Q*_{2} = {*q*_{2},
*q*_{4}} *(having output y). Then, the transitions using the classification become:*

Q | Q_{1} | Q_{2} | ||||
---|---|---|---|---|---|---|

T | →q_{1} | q_{5} | q_{7} | q_{2} | q_{4} | |

a | Q_{2} | Q_{2} | Q_{2} | Q_{1} | Q_{1} | |

b | Q_{1} | Q_{2} | Q_{1} | Q_{2} | Q_{2} |

*Then, Q*_{1} *is divided into two subclasses, therefore
C*_{2} = {*Q*_{11}, *Q*_{12},
*Q*_{2}} *where Q*_{11} = {*q*_{1},
*q*_{7}} *and Q*_{12} = {*q*_{5}}.
*Then, we have:*

Q | Q_{11} | Q_{12} | Q_{2} | |||
---|---|---|---|---|---|---|

T | →q_{1} | q_{7} | q_{5} | q_{2} | q_{4} | |

a | Q_{2} | Q_{2} | Q_{2} | Q_{12} | Q_{12} | |

b | Q_{11} | Q_{11} | Q_{2} | Q_{2} | Q_{2} |

*Thus C*_{3} = *C*_{2}, *and we can describe the minimal Moore
automaton as follows:*

V | x | x | y |
---|---|---|---|

T Q | →Q_{11} | Q_{12} | Q_{2} |

a | Q_{2} | Q_{2} | Q_{12} |

b | Q_{11} | Q_{2} | Q_{2} |

We note here that the minimization methods for finite automata presented in this book are using the Aufenkamp-Hohn algorithm.

**Exercise 45.** *A Moore automaton A is given by the following Cayley table:*

V | x | x | y | z | z | y |
---|---|---|---|---|---|---|

T Q | →q_{0} | q_{1} | q_{2} | q_{3} | q_{4} | q_{5} |

a | q_{4} | q_{5} | q_{3} | q_{0} | q_{4} | q_{5} |

b | q_{1} | q_{2} | q_{4} | q_{5} | q_{5} | q_{5} |

*Give the same automaton by a graph. What is the output of the automaton for the input words *

*
abbaab and
bbaabbaabbbb?
*

**Exercise 46.** *The Moore automaton A is defined by the graph shown in
Figure 2.14. *

*Give it by a Cayley table. Give its output for the input*

*
cabbaccc,
aabbccabcabcbbcaca and
acaabacbbbcccaa.
*

**Exercise 47.** *The Moore automata A is defined by its Cayley table as follows:*

V | 0 | 1 | 0 | 2 | 0 | 2 | 0 | 1 | 1 |
---|---|---|---|---|---|---|---|---|---|

T Q | →q_{1} | q_{2} | q_{3} | q_{4} | q_{5} | q_{6} | q_{7} | q_{8} | q_{9} |

a | q_{1} | q_{5} | q_{8} | q_{5} | q_{9} | q_{1} | q_{2} | q_{3} | q_{3} |

b | q_{2} | q_{4} | q_{6} | q_{2} | q_{6} | q_{8} | q_{4} | q_{5} | q_{1} |

c | q_{3} | q_{9} | q_{8} | q_{2} | q_{8} | q_{8} | q_{7} | q_{6} | q_{8} |

*Find a minimal Moore automaton that is equivalent to A. *

**Exercise 48.** *The Moore automata A is defined by its Cayley table as follows:*

V | x | y | y | y | z | z |
---|---|---|---|---|---|---|

T Q | →q_{1} | q_{2} | q_{3} | q_{4} | q_{5} | q_{6} |

a | q_{2} | q_{4} | q_{4} | q_{2} | q_{2} | q_{3} |

b | q_{3} | q_{2} | q_{6} | q_{4} | q_{6} | q_{5} |

*Give the minimal Moore automaton that is equivalent to A. *

Finally, we devote this subsection to a brief analysis of the mappings
*T*^{*} → *V*^{*}
that can be obtained by the Mealy and the Moore automata.

We provide a theorem that the classes of the Mealy and the Moore automata have the same efficiency.

**Theorem 9.** (Gill's theorem). *For every Mealy automaton there exists an equivalent
Moore automaton and for every Moore automaton there exists an equivalent Mealy automaton. *

For a Moore automaton there is a very simple way to construct a Mealy automaton that defines the
same mapping from *T*^{*} to *V*^{*}.
Roughly speaking, the output letter should move from a state to
each of the transitions (arrows in the graph) into the
given state. The other direction, that is not detailed here, can be done my multiplying the number
of states (using the set *Q* × *V*).

Now let us see some of the important properties of the mappings that can be defined by finite transducers.

**Theorem 10.** (Raney's theorem). *The automata mappings have the following two properties:*

*They are length preserving, i.e., for any input string w*∈*T*^{*}*its length is the same as the length of the output u*∈*V*^{*}given by w.*They are prefix keeping, i.e., the image of the prefix will also be prefix, more formally: for every w,v*∈*T*^{*}*the output for the string wv will start with the output string assigned to w.*

We note here that there are automata mappings that cannot be defined by the finite state Mealy or Moore automata, but only by their infinite state variants. We have chosen not to discuss these infinite variants in our book.