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 tuple:

$$\mathcal{T}=(Q,\Sigma ,\Gamma ,\delta ,\lambda ,q_0,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
• $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, using the transition function $\delta$, and an output symbol, using the output function $\lambda$, are produced by the transducer.

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 \lambda (Q,\Sigma )$ is the output. Both can can be a vector, e.g.: when adding binary numbers, a 2D vector is used as input.

Translation Relation

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

Note that ${\delta }^{\ast }$ is the extended transition relation of automaton $\mathcal{T}$.

Examples

Binary Addition