Automata with Output: Moore, Mealy, finite Transducer

The name Moore machine comes from that of its promoter, Edward F. Moore, who wrote 1956 "Gedanken-experiments on Sequential Machines" (cf. [205]).

A Moore machine can be defined as

$$\langle Q, I, F, \Sigma, \Xi, \Delta, \Lambda \rangle$$

with

1. $Q$ := Finite set of states
2. $I \subseteq Q$ := Set of initial states
3. $F \subseteq Q$ := Set of final states
4. $\Sigma$ := Finite set of symbols forming the input alphabet
5. $\Xi$ := Finite set of symbols forming the output alphabet
6. $\Delta \subseteq Q \times \Sigma \times Q$ := Set of state transitions
7. $\Lambda \subseteq Q \times \Xi$ := Set of output transitions

The number of states in a Moore machine will be greater than or equal to the number of states in the corresponding Mealy machine.

The name Mealy machine comes from that of the concept's promoter, G. H. Mealy, who wrote 1955 "A Method for Synthesizing Sequential Circuits" (cf. [197])

A Mealy machine can be defined as

$$\langle Q, I, F, \Sigma, \Xi, \Delta, \Lambda \rangle$$

with

1. $Q$ := Finite set of states
2. $I \subseteq Q$ := Set of initial states
3. $F \subseteq Q$ := Set of final states
4. $\Sigma$ := Finite set of symbols forming the input alphabet
5. $\Xi$ := Finite set of symbols forming the output alphabet
6. $\Delta \subseteq Q \times \Sigma \times Q$ := Set of state transitions
7. $\Lambda \subseteq Q \times \Sigma \times \Xi$ := Set of output transitions

Th: If $A_{1}$ is a mealy automaton and $A_{2}$ a moore automaton than $A_{1}$ and $A_{2}$ are equivalent (see Hopcroft and Ullman [137]:p.44).

An interesting generalization of a mealy automaton is the Finite Transducer (cf. Yu (1997)[300]:P66f):

$$\langle Q, I, F, \Sigma, \Xi, \Delta, \rangle$$

with

1. $Q$ := Finite set of states
2. $I \subseteq Q$ := Set of initial states
3. $F \subseteq Q$ := Set of final states
4. $\Sigma$ := Finite set of symbols forming the input alphabet
5. $\Xi$ := Finite set of symbols forming the output alphabet
6. $\Delta \subseteq Q \times \Sigma^{*} \times Q \times \Xi^{*}$ := Set of state and output transitions

A finite trasducer is called to be in a standard form if one uses a function $\delta$ instead of the relation $\Delta$ and it holds: $\delta: Q \times \Sigma \cup \{\epsilon\} \longrightarrow 2^{Q \times (\Xi \cup \{\epsilon\}) }$

Th: Each finite transducer can be transformed into an equivalent finite transducer in the standard form (cf. (cf. Yu (1997)[300]:P69):