Finite-state transducer

Remarks

Example: with $\Sigma = \set{a}$, $\Gamma = \set{b}$, $Q = \set{0, 1}$, $I = F = \set{0}$ and $E = \set{(0, a, b, 1), (1, \varepsilon, b, 0)}$, the paths from $0$ to $0$ go around the loop $k$ times, so the relation is $\set{(a^k, b^{2k}) : k \ge 0}$. Non-example: a device with one transition $(0, a, b^n, 0)$ for every $n \ge 0$ fails clause 4, since $E$ must be finite and its labels must be single symbols or $\varepsilon$. The relation $\set{(a, b^n) : n \ge 0}$ is still the relation of a finite-state transducer, for example with $E = \set{(0, a, \varepsilon, 1), (1, \varepsilon, b, 1)}$, $I = \set{0}$ and $F = \set{1}$. Forgetting the output labels gives an NFA with $\varepsilon$-moves for the input projection of the relation. Some authors allow whole words as transition labels; this gives the same relations.