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:

$$\mathcal{T}=(Q,\Sigma ,\Gamma ,\delta ,\lambda ,I,F)$$

where:

• $Q$ is a set of states.
• $\Sigma$ is the input alphabet.
• $\Gamma$ is the output alphabet.
• $\delta :Q\times \Sigma \to Q$ is the transition function.
• $\lambda :Q\times \Sigma \to \Gamma$ is the output function (for Mealy machines).
• $I\subseteq Q$ is the set of initial states.
• $F\subseteq Q$ is the set of accepting (final) states.

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

Notation

When representing a transducer, the $a/b$ notation is used to describe state transitions, where $a\in \Sigma$ is the input, and $b\in \Gamma$ 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 $[\mathcal{T}]$ defined by a transducer is the set of all input-output pairs $(w,w^{\prime })$ such that the transducer can process $w$ and produce $w^{\prime }$ while ending in an accepting state:

$$[\mathcal{T}]=\{(w,w^{\prime })\in {\Sigma }^{\_}\times {\Gamma }^{\_}\mid (i,w,w^{\prime },f)\in {\delta }^{\ast },i\in I,f\in F\}$$

Note that ${\delta }^{\ast }$ 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).