Transducer

automata-theory

Definition

Transducer

A transducer is an automaton that processes input strings and produces corresponding output strings, effectively mapping one sequence to another.

Formally, a finite-state transducer can be defined as a septuple:

where:

• is a set of states.
• is the input alphabet.
• is the output alphabet.
• is the transition function.
• is the output function (for Mealy machines).
• is the set of initial states.
• is the set of accepting (final) states.

For each input symbol in a state, a next state is determined by , and an output symbol is produced by .

Notation

When representing a transducer, the notation is used to describe state transitions, where is the input, and is the output. Both can be a vector; for instance, when adding binary numbers, a 2D vector is used as input.

Translation Relation

The translation relation defined by a transducer is the set of all input-output pairs such that the transducer can process and produce while ending in an accepting state:

Note that here refers to the extended transition relation of the transducer.

Examples

Binary Addition

The following transducer performs bitwise binary addition (processing from least significant bit to most significant bit).