rational transducer
Definition
A rational transducer is a generalization^{} of a generalized sequential machine (gsm). Recall that a gsm $M$ is a quadruple $(S,\mathrm{\Sigma},\mathrm{\Delta},\tau )$ where $S$ is a finite set^{} of states, $\mathrm{\Sigma}$ and $\mathrm{\Delta}$ are the input and output alphabets respectively, and $\tau $ is the transition function taking an input symbol from one state to an output word in another state. A rational transducer has all of the components^{} above, except that the transition function $\tau $ is more general: its domain consists of a pair of a state and an input word, rather than an input symbol.
Formally, a rational transducer $M$ is a quadruple $(S,\mathrm{\Sigma},\mathrm{\Delta},\tau )$ where $S,\mathrm{\Sigma},\mathrm{\Delta}$ are defined just as those in a gsm, except that the transition function $\tau $ has domain a finite subset of $S\times {\mathrm{\Sigma}}^{*}$ such that $\tau (s,u)$ is finite for each $(s,u)\in \mathrm{dom}(\tau )$. One can think of $\tau $ as a finite subset of $S\times {\mathrm{\Sigma}}^{*}\times S\times {\mathrm{\Delta}}^{*}$, or equivalently a finite relation^{} between $S\times {\mathrm{\Sigma}}^{*}$ and $S\times {\mathrm{\Delta}}^{*}$.
Like a gsm, a rational transducer can be turned into a language^{} acceptor by fixing an initial state ${s}_{0}\in S$ and a nonempty set $F$ of finite states $F\subseteq S$. In this case, a rational transducer turns into a 6tuple $(S,\mathrm{\Sigma},\mathrm{\Delta},\tau ,{s}_{0},F)$. An input configuration^{} $({s}_{0},u)$ is said to be initial, and an output configuration $(t,v)$ is said to be final if $t\in F$. The language accepted by a rational transducer $M$ is defined as the set
$$L(M):=\{u\in {\mathrm{\Sigma}}^{*}\mid \tau ({s}_{0},u)\text{contains an final output configuration.}\}.$$ 
Rational Transductions
Additionally, like a gsm, a rational transducer can be made into a language translator. The initial state ${s}_{0}$ and the set $F$ of final states are needed. Given a rational transducer $M$, for every input word $u$, let
$${\mathrm{RT}}_{M}(u):=\{v\in {\mathrm{\Delta}}^{*}\mid (t,v)\in \tau ({s}_{0},u)\text{is a final output configuration.}\}.$$ 
Thus, ${\mathrm{RT}}_{M}$ is a function^{} from ${\mathrm{\Sigma}}^{*}$ to $P({\mathrm{\Delta}}^{*})$, and is called the rational transduction (defined) for the rational transducer $M$. The rational transduction for $M$ can be extended: for any language $L$ over the input alphabet $\mathrm{\Sigma}$,
$${\mathrm{RT}}_{M}(L):=\bigcup \{{\mathrm{RT}}_{M}(u)\mid u\in L\}.$$ 
In this way, ${\mathrm{RT}}_{M}$ may be thought of as a language translator.
As with GSM mappings, one can define the inverse^{} of a rational transduction, given a rational transduction ${\mathrm{RT}}_{M}$:
$${\mathrm{RT}}_{M}^{1}(v):=\{u\mid v\in {\mathrm{RT}}_{M}(u)\}\mathit{\hspace{1em}}\text{and}\mathit{\hspace{1em}}{\mathrm{RT}}_{M}^{1}(L):=\bigcup \{{\mathrm{RT}}_{M}^{1}(v)\mid v\in L\}.$$ 
Here are some examples of rational transductions

•
Every GSM mapping is clearly a rational transduction, since every gsm is a rational transducer. As a corollary, any homomorphism^{}, as well as intersection^{} with any regular language, is a rational transduction.

•
The inverse of a rational transduction is a transduction. Given any rational transducer $M=(S,\mathrm{\Sigma},\mathrm{\Delta},\tau ,{s}_{0},F)$, define a rational transducer ${M}^{\prime}=({S}^{\prime},\mathrm{\Delta},\mathrm{\Sigma},{\tau}^{\prime},{t}_{0},{F}^{\prime})$ as follws: ${S}^{\prime}=S\stackrel{\cdot}{\cup}\{{t}_{0}\}$ (where $\stackrel{\cdot}{\cup}$ denotes disjoint union^{}), ${F}^{\prime}=\{{s}_{0}\}$, and ${\tau}^{\prime}\subseteq S\times {\mathrm{\Delta}}^{*}\times S\times {\mathrm{\Sigma}}^{*}$ is given by
$${\tau}^{\prime}(t,v)=\{\begin{array}{cc}\{(s,v)\mid (s,v)\text{is a final output configuration of}M\}\hfill & \text{if}t={t}_{0}\hfill \\ \{(s,u)\mid (t,v)\in \tau (s,u)\}\hfill & \text{otherwise.}\hfill \end{array}$$ As $\tau $ is finite, so is ${\tau}^{\prime}$, so that ${M}^{\prime}$ is welldefined. In addition, ${\mathrm{RT}}_{{M}^{\prime}}={\mathrm{RT}}_{M}^{1}$. As a corollary, the inverse homomorphism is a rational transduction.

•
The composition^{} of two rational transductions is a rational transduction. To see this, suppose ${M}_{1}=({S}_{1},{\mathrm{\Sigma}}_{1},{\mathrm{\Delta}}_{1},{\tau}_{1},{s}_{1},{F}_{1})$ and ${M}_{2}=({S}_{2},{\mathrm{\Sigma}}_{2},{\mathrm{\Delta}}_{2},{\tau}_{2},{s}_{2},{F}_{2})$ are two rational transducers such that ${\mathrm{\Delta}}_{1}\subseteq {\mathrm{\Sigma}}_{2}$. Define $M=(S,{\mathrm{\Sigma}}_{1},{\mathrm{\Delta}}_{2},\tau ,{s}_{1},{F}_{2})$ as follows: $S={S}_{1}\stackrel{\cdot}{\cup}{S}_{2}$, and $\tau \subseteq S\times {\mathrm{\Sigma}}_{1}^{*}\times S\times {\mathrm{\Delta}}_{2}^{*}$ is given by
$$\tau (s,u)=\{\begin{array}{cc}{\tau}_{1}(s,u)\hfill & \text{if}(s,u)\in {S}_{1}\times {\mathrm{\Sigma}}_{1}^{*}\hfill \\ {\tau}_{2}(s,u)\hfill & \text{if}(s,u)\in {S}_{2}\times {\mathrm{\Sigma}}_{2}^{*}\hfill \\ \{({s}_{2},u)\}\hfill & \text{if}(s,u)\text{is a final output configuration of}{M}_{1}\hfill \\ \mathrm{\varnothing}\hfill & \text{otherwise.}\hfill \end{array}$$ Again, since both ${\tau}_{1}$ and ${\tau}_{2}$ are finite, so is $\tau $, and thus $M$ welldefined. In addition, ${\mathrm{RT}}_{M}={\mathrm{RT}}_{{M}_{2}}\circ {\mathrm{RT}}_{{M}_{1}}$.
A family $\mathcal{F}$ of languages is said to be closed under rational transduction if for every $L\in \mathcal{F}$, and any rational transducer $M$, we have ${\mathrm{RT}}_{M}(L)\in \mathcal{F}$. The three properties above show that if $\mathcal{F}$ is closed under rational transduction, it is a cone. The converse^{} is also true, as it can be shown that every rational transduction can be expressed as a composition of inverse homomorphism, intersection with a regular language, and homomorphism. Thus, a family of languages being closed under rational transduction completely characterizes a cone.
References
 1 A. Salomaa Computation and Automata, Encyclopedia of Mathematics and Its Applications, Vol. 25. Cambridge (1985).
Title  rational transducer 

Canonical name  RationalTransducer 
Date of creation  20130322 18:59:29 
Last modified on  20130322 18:59:29 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  12 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03D05 
Classification  msc 68Q45 
Related topic  GeneralizedSequentialMachine 
Defines  rational transduction 