Finite-State Transducers: Mealy & Moore Machines

A finite-state acceptor reduces a complete input word to one Boolean answer. A finite-state transducer exposes behavior while it runs: it maps an input trace to an output trace or output word, using finite state to remember only the history relevant to future outputs. That change makes timing, output length, partiality, and observability part of the model rather than diagram decoration.

Mealy and Moore machines are the foundational synchronous forms. They can implement closely related behavior, but only after the interface declares whether an initial Moore output is observable and how outputs align with consumed inputs. More general finite-state transducers may emit strings, define partial functions or relations, and compose through an intermediate alphabet.

Fix the interface before naming the machine #

Four independent choices determine what a transducer means:

Acceptance is another choice. A total synchronous Mealy or Moore machine often produces output for every input and needs no final states. A string transducer commonly uses initial/final states to define only successful input/output pairs. Mixing those conventions silently makes trace claims impossible to check.

Mealy machines put output on transitions #

When the machine is in $q$ and consumes $a$, it emits $\lambda(q,a)$ and moves to $\delta(q,a)$. An edge label a / x therefore means “consume a, emit x.” For input $a_1\cdots a_n$, define

$$q_i=\delta(q_{i-1},a_i), \qquad b_i=\lambda(q_{i-1},a_i).$$

The output word is $b_1\cdots b_n$, so this narrow synchronous model emits exactly one symbol per consumed symbol.

Worked Mealy machine: running parity #

The input alphabet is $\{0,1\}$; after each bit, emit 0 if the number of 1 symbols seen so far is even and 1 if it is odd. State $E$ means even before the next input, and $O$ means odd.

flowchart LR
  start([start]) --> E(("E"))
  E -- "0 / 0" --> E
  E -- "1 / 1" --> O(("O"))
  O -- "0 / 1" --> O
  O -- "1 / 0" --> E

For input 1011, the trace is:

Thus the output is 1101. The proof is the state invariant: before each step, the state records the parity of the prefix already consumed; the transition toggles it exactly on input 1, and the edge output reports the new parity.

Moore machines put output on states #

In Moore's classical discrete-time model, the initial state already has an output. For input $a_1\cdots a_n$,

$$q_i=\delta(q_{i-1},a_i), \qquad \text{full output}=\omega(q_0)\omega(q_1)\cdots\omega(q_n).$$

The parity machine becomes two state-labeled nodes, $E/0$ and $O/1$, with input-only edges. On 1011 its full output is 0·1101: the leading 0 is the initial state's output, followed by one post-transition output per input symbol.

Converting between Mealy and Moore representations #

The conversions preserve a declared external behavior, not a bare diagram.

Moore to Mealy #

If comparison uses the destination's post-input output, replace

$$q\xrightarrow{a}q'$$

with a Mealy edge

$$q\xrightarrow{a/\omega(q')}q'.$$

After each input, both machines reach $q'$ and report $\omega(q')$. The initial Moore output remains outside the Mealy edge trace and must be suppressed, exposed separately, or encoded through a special interface event.

Mealy to Moore #

A Moore state has one fixed output. If Mealy transitions entering the same state carry different outputs, that destination must be split into output-distinguished copies.

Consider this Mealy machine:

The two transitions into $Q$ emit different symbols. One Moore state labeled $Q/x$ would misrepresent the b transition; one labeled $Q/y$ would misrepresent the a transition. Create $Q_x/x$ and $Q_y/y$ and redirect each incoming transition to the copy carrying its output. All outgoing transitions are duplicated according to the underlying Mealy state. Only $P_x/x$ is needed for reachable post-input behavior because every transition entering $P$ emits x.

flowchart LR
  subgraph M["Mealy destination"]
    P(("P")) -- "a / x" --> Q(("Q"))
    P -- "b / y" --> Q
  end
  C["one Moore state<br/>has one fixed output"]
  subgraph N["Split Moore destinations"]
    QX(("Qx / x"))
    QY(("Qy / y"))
  end
  Q --> C
  C --> QX
  C --> QY

A new initial Moore state or a declared initial-output convention is still required, because no incoming Mealy transition determines an output before the first input.

Correctness is an induction on input prefixes: after the same prefix, the Moore copy records both the underlying Mealy state and the last emitted Mealy symbol; therefore its state output matches that last edge output. Remove unreachable copies only after this invariant has been established.

Behavioral equivalence is stronger than matching samples #

Machine isomorphism preserves internal state structure up to renaming. Behavioral equivalence asks only whether the machines produce the same observable output for every permitted input under the same timing and partiality convention. Non-isomorphic machines can be behaviorally indistinguishable.

Two states of a deterministic transducer are behaviorally equivalent when every future input produces the same future output behavior from them. A partition-refinement minimizer makes this executable:

1. Remove unreachable states.
2. Initially separate states by immediately observable behavior:
   • Moore states by their state outputs;
   • Mealy states by the vector of outputs emitted for each input.
3. Split a block whenever an input sends its members into different current blocks.
4. Stop when no split occurs; merge each stable block.

If two states split, retain the input symbol and predecessor distinction. Recursing backward reconstructs a distinguishing input word—a concrete trace on which the states differ.

For a partial machine, undefined input must have declared semantics. “No output,” rejection, an error symbol, and absence from the denoted function are different observations and yield different equivalence classes.

Sequential transducers may emit strings #

Mohri's sequential model generalizes the Mealy edge output from one symbol to a word in $\Gamma^*$ and allows partial transitions. Along a unique input path, concatenate transition outputs in order. A subsequential extension additionally associates an output word with a successful final state.

A useful abstract form has:

• finite states and designated initial/final states;
• a partial deterministic transition function on input symbols;
• an output word on each defined transition;
• for a subsequential machine, a final-output word on each successful final state.

The denoted mapping is partial: an input has an output only when all required transitions exist and the run ends successfully.

Worked example: an escape encoder #

Use a one-state sequential transducer whose input and output alphabets contain the symbols a and #:

It maps a#a to a##a. The machine is deterministic and total, but it is not a synchronous one-symbol-output Mealy machine: the # transition emits two symbols. No final output is needed.

Zero-length edge output is also possible in this model. That output is the empty word; it is not the same as an undefined transition.

Determinism, functionality, and relations are separate #

A general finite-state transducer can have multiple paths for one input and can therefore denote a relation

$$R\subseteq\Sigma^*\times\Gamma^*.$$

Several properties must not be collapsed:

Input-deterministic

At most one relevant transition/path choice is available for each next input from a state.

Functional

Every input in the relation's domain is paired with at most one output, even if several successful paths exist.

Total

Every input word in the stated input universe has an output.

Sequential or subsequential

The function has a deterministic finite-state realization of the corresponding form.

Input determinism implies functionality for a correctly defined deterministic output path, but the converse is false: Mohri shows that not every functional rational transducer is sequential or subsequential. A nondeterministic transducer may have several successful paths that happen to agree on output, yet no equivalent deterministic sequential machine of that class exists.

Composition connects an output alphabet to an input alphabet #

If $T_1$ maps $\Sigma^*$ to $\Gamma^*$ and $T_2$ maps $\Gamma^*$ to $\Delta^*$, their composition is

$$(T_2\circ T_1)(w)=T_2(T_1(w)),$$

where defined. The order is directional: $T_1$ runs first.

In the simplest synchronous case, a composite state is $(q_1,q_2)$. On external symbol $a$:

1. $T_1$ consumes $a$, emits $b$, and moves to $q_1'$.
2. $T_2$ consumes $b$, emits $c$, and moves to $q_2'$.
3. The composite emits $c$ and moves to $(q_1',q_2')$.

The invariant is that after any external prefix, the pair contains exactly the states reached by first processing that prefix through $T_1$ and then processing its complete intermediate output through $T_2$.

Independent cascade example #

$T_1$ normalizes a to x and b to y; $T_2$ classifies x as 0 and y as 1. Then input abba produces intermediate xyyx and external output 0110.

flowchart LR
  I["external input<br/>a b b a"] --> T1["T1 · normalize"]
  T1 -->|"x y y x"| T2["T2 · classify"]
  T2 --> O["external output<br/>0 1 1 0"]

For variable-length output, one $T_1$ edge may make $T_2$ traverse several edges; epsilon input/output labels make path alignment more delicate. Mohri's constructive closure result handles composition of sequential and $p$-subsequential functions with the required paired-state bookkeeping. A naive “advance both machines once” rule is valid only for the synchronous one-symbol interface.

Automata products and decomposition separates cascade composition from shared-input parallel products in detail.

Weighted transducers are a separate layer #

OpenFst's official representation puts an input label, output label, and weight on each arc; an acceptor is represented as the special case in which input and output labels are equal. Composition matches compatible intermediate labels while preserving the external labels and combining weights according to the configured weight algebra.

That is a useful implementation bridge, not a complete theory. To reason correctly about weighted paths one must define the weight set, choice/combination operations, path aggregation, epsilon filtering, and algorithm preconditions. Shortest paths, determinization, minimization, and speech/language applications belong in a dedicated weighted-FST chapter rather than being hidden behind the word “weight.”

Diagnostic checklist #

• Is output attached to a transition or a state?
• Is the initial Moore output observable, suppressed, or encoded separately?
• Are Mealy and Moore traces compared at the same time instants?
• Does a Mealy-to-Moore conversion split destinations reached with different outputs?
• Is each transition output one symbol, a word, or possibly $\varepsilon$?
• Does final acceptance or a final output participate in the mapping?
• Is the machine total, partial, or relational on its declared input universe?
• Does “functional” actually mean one output per input, rather than one path?
• Are undefined transitions given an explicit external meaning before equivalence is tested?
• In a composition, does the first output alphabet match the second input alphabet?
• If intermediate outputs have variable length or epsilon labels, is the construction more precise than lockstep pair stepping?
• Are parallel product and cascade being kept distinct?

The durable lesson is that a transducer is an observable contract over traces. State placement and diagram style are secondary. Once timing, output granularity, path policy, and partiality are explicit, conversion, minimization, and composition become proof obligations over that contract rather than informal rewiring exercises.