We start by giving the formal definition of Mealy automata.

Definition 17. A Mealy automaton is an ordered sextuple A = (Q, T, V, q₀, δ, μ), where Q, T, q₀, δ 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₀ ∈ 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

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

2.11. ábra - The graph of the Mealy automaton of Example 30.

Let us make some sample runs of the automaton:

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

Animation 6.

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₁[p] = C₁[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:

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₁ = {Q₁, Q₂}, where Q₁ = {q₁, q₃, q₅, q₆} (having output x for input a and output y for input b) and Q₂ = {q₂, q₄} (having output z for input a and output y for input b). Then, the transition function reflecting this classification is as follows:

Then, Q₁ is divided into two subgroups in the classification C₂ = {Q₁₁, Q₁₂, Q₂} with Q₁₁ = {q₁, q₅} and Q₁₂ = {q₃, q₆}. (Q₂ = {q₂, q₄} remains the same group.) The transition function reflecting these groups is as follows:

Only Q₁₂ is divided (to its elements) and thus C₃ = {Q₁₁, Q₁₂₁, Q₁₂₂, Q₂} with Q₁₂₁ = {q₃} and Q₁₂₂ = {q₅}. Then the transitions become:

Since C₄ = C₃, we can give the minimal Mealy automaton (writing also the values of the output function into the table):

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

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.

2.12. ábra - The graph of the Mealy automaton of Exercise 42.

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:

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

In this subsection another type of finite transducers are investigated.

Definition 18. A Moore automaton is an ordered sextuple A = (Q, T, V, q₀, δ, η), where Q, T, V, q₀, δ 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.

2.13. ábra - The graph of the Mealy automaton of Exercise 33.

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

aabb, 
baabaa and 
abaababb.

Solution:

The example runs give the outputs as follows:

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

Animation 7.

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₁ 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:

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₃ and q₆ are not reachable, therefore we erase them. We need to minimize the automaton

Classification C₁ = {Q₁, Q₂} is based on the output function: Q₁ = {q₁, q₅, q₇} (having output x) and Q₂ = {q₂, q₄} (having output y). Then, the transitions using the classification become:

Then, Q₁ is divided into two subclasses, therefore C₂ = {Q₁₁, Q₁₂, Q₂} where Q₁₁ = {q₁, q₇} and Q₁₂ = {q₅}. Then, we have:

Thus C₃ = C₂, and we can describe the minimal Moore automaton as follows:

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:

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.

2.14. ábra - The graph of the Mealy automaton of Exercise 46.

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:

Find a minimal Moore automaton that is equivalent to A.

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

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:

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.