## 2.5. Finite Transducers

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.

### 2.5.1. Mealy Automata

We start by giving the formal definition of Mealy automata.

Definition 17. A Mealy automaton is an ordered sextuple A = (Q, T, V, q0, δ, μ), where Q, T, q0, δ 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, q0 ∈ 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 xV 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 Qq1q2q3q4
a(q4, x)(q3, y)(q1, y)(q2, x)
a(q1, y)(q1, x)(q2, x)(q2, y)
a(q1, x)(q1, x)(q4, y)(q3, y)

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:

• 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.

Animation 6.

We say that two Mealy automata are equivalent if they assign the same output word for every input word uT*. 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., C1[p] = C1[q] if and only if for every input letter aT 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 Qq1q2q3q4q5q6
a(q2, x)(q1, z)(q6, x)(q5, z)(q4, x)(q5, x)
b(q3, y)(q2, y)(q4, y)(q4, y)(q3, y)(q2, 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 C1 = {Q1, Q2}, where Q1 = {q1, q3, q5, q6} (having output x for input a and output y for input b) and Q2 = {q2, q4} (having output z for input a and output y for input b). Then, the transition function reflecting this classification is as follows:

QQ1Q2
T q1q3q5q6q2q4
aQ2Q1Q2Q1Q1Q1
bQ1Q2Q1Q2Q2Q2

Then, Q1 is divided into two subgroups in the classification C2 = {Q11, Q12, Q2} with Q11 = {q1, q5} and Q12 = {q3, q6}. (Q2 = {q2, q4} remains the same group.) The transition function reflecting these groups is as follows:

QQ11Q12Q2
T q1q5q3q6q2q4
aQ2Q2Q11Q12Q11Q11
bQ12Q12Q2Q2Q2Q2

Only Q12 is divided (to its elements) and thus C3 = {Q11, Q121, Q122, Q2} with Q121 = {q3} and Q122 = {q5}. Then the transitions become:

QQ11Q121Q122Q2
T q1q5q3q6q2q4
aQ2Q2Q11Q122Q11Q11
bQ121Q121Q2Q2Q2Q2

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

T QQ11Q121Q122Q2
a(Q2, x)(Q11, x)(Q122, x)(Q11, z)
b(Q121, y)(Q2, x)(Q2, y)(Q2, y)

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

T Qq0q1q2q3
0(q0, a)(q3, a)(q1, b)(q2, b)
1(q1, b)(q1, a)(q2, b)(q2, 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.

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:

T Qq1q2q3q4q5q6q7q8
a(q8, 0)(q3, 1)(q8, 0)(q1, 1)(q8, 0)(q4, 0)(q3, 1)(q5, 1)
b(q2, 1)(q1, 0)(q7, 0)(q2, 1)(q7, 1)(q2, 1)(q6, 0)(q3, 1)

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

T Qq1q2q3q4q5
a(q2, x)(q2, y)(q2, x)(q5, y)(q4, y)
b(q4, x)(q3, x)(q1, x)(q3, x)(q3, x)
c(q5, y)(q5, x)(q1, y)(q5, x)(q2, x)

### 2.5.2. Moore Automata

In this subsection another type of finite transducers are investigated.

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

V0101
T Qq0q1q2q3
aq2q3q0q3
bq1q2q3q2

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.

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 uT* 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 C1 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:

Vxyyyxxx
T Qq1q2q3q4q5q6q7
aq2q5q1q5q2q3q4
bq7q4q6q2q4q6q1

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

Vxyyxx
T Qq1q2q4q5q7
aq2q5q5q2q4
bq7q4q2q4q1

Classification C1 = {Q1, Q2} is based on the output function: Q1 = {q1, q5, q7} (having output x) and Q2 = {q2, q4} (having output y). Then, the transitions using the classification become:

QQ1Q2
T q1q5q7q2q4
aQ2Q2Q2Q1Q1
bQ1Q2Q1Q2Q2

Then, Q1 is divided into two subclasses, therefore C2 = {Q11, Q12, Q2} where Q11 = {q1, q7} and Q12 = {q5}. Then, we have:

QQ11Q12Q2
T q1q7q5q2q4
aQ2Q2Q2Q12Q12
bQ11Q11Q2Q2Q2

Thus C3 = C2, and we can describe the minimal Moore automaton as follows:

Vxxy
T QQ11Q12Q2
aQ2Q2Q12
bQ11Q2Q2

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:

Vxxyzzy
T Qq0q1q2q3q4q5
aq4q5q3q0q4q5
bq1q2q4q5q5q5

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:

V010202011
T Qq1q2q3q4q5q6q7q8q9
aq1q5q8q5q9q1q2q3q3
bq2q4q6q2q6q8q4q5q1
cq3q9q8q2q8q8q7q6q8

Find a minimal Moore automaton that is equivalent to A.

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

Vxyyyzz
T Qq1q2q3q4q5q6
aq2q4q4q2q2q3
bq3q2q6q4q6q5

Give the minimal Moore automaton that is equivalent to A.

### 2.5.3. Automata Mappings

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 wT* its length is the same as the length of the output uV* given by w.

• They are prefix keeping, i.e., the image of the prefix will also be prefix, more formally: for every w,vT* 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.