You are here
Homerational transducer
Primary tabs
rational transducer
Definition
A rational transducer is a generalization of a generalized sequential machine (gsm). Recall that a gsm $M$ is a quadruple $(S,\Sigma,\Delta,\tau)$ where $S$ is a finite set of states, $\Sigma$ and $\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,\Sigma,\Delta,\tau)$ where $S,\Sigma,\Delta$ are defined just as those in a gsm, except that the transition function $\tau$ has domain a finite subset of $S\times\Sigma^{*}$ such that $\tau(s,u)$ is finite for each $(s,u)\in\operatorname{dom}(\tau)$. One can think of $\tau$ as a finite subset of $S\times\Sigma^{*}\times S\times\Delta^{*}$, or equivalently a finite relation between $S\times\Sigma^{*}$ and $S\times\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,\Sigma,\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\Sigma^{*}\mid\tau(s_{0},u)\mbox{ 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
$\operatorname{RT}_{M}(u):=\{v\in\Delta^{*}\mid(t,v)\in\tau(s_{0},u)\mbox{ is a% final output configuration.}\}.$ 
Thus, $\operatorname{RT}_{M}$ is a function from $\Sigma^{*}$ to $P(\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 $\Sigma$,
$\operatorname{RT}_{M}(L):=\bigcup\{\operatorname{RT}_{M}(u)\mid u\in L\}.$ 
In this way, $\operatorname{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 $\operatorname{RT}_{M}$:
$\operatorname{RT}_{M}^{{1}}(v):=\{u\mid v\in\operatorname{RT}_{M}(u)\}\quad% \mbox{ and }\quad\operatorname{RT}_{M}^{{1}}(L):=\bigcup\{\operatorname{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,\Sigma,\Delta,\tau,s_{0},F)$, define a rational transducer $M^{{\prime}}=(S^{{\prime}},\Delta,\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\Delta^{*}\times S\times\Sigma^{*}$ is given by
$\tau^{{\prime}}(t,v)=\left\{\begin{array}[]{ll}\{(s,v)\mid(s,v)\mbox{ is a % final output configuration of }M\}&\textrm{if }t=t_{0}\\ \{(s,u)\mid(t,v)\in\tau(s,u)\}&\textrm{otherwise.}\end{array}\right.$ As $\tau$ is finite, so is $\tau^{{\prime}}$, so that $M^{{\prime}}$ is welldefined. In addition, $\operatorname{RT}_{{M^{{\prime}}}}=\operatorname{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},\Sigma_{1},\Delta_{1},\tau_{1},s_{1},F_{1})$ and $M_{2}=(S_{2},\Sigma_{2},\Delta_{2},\tau_{2},s_{2},F_{2})$ are two rational transducers such that $\Delta_{1}\subseteq\Sigma_{2}$. Define $M=(S,\Sigma_{1},\Delta_{2},\tau,s_{1},F_{2})$ as follows: $S=S_{1}\stackrel{\cdot}{\cup}S_{2}$, and $\tau\subseteq S\times\Sigma_{1}^{*}\times S\times\Delta_{2}^{*}$ is given by
$\tau(s,u)=\left\{\begin{array}[]{ll}\tau_{1}(s,u)&\textrm{if }(s,u)\in S_{1}% \times\Sigma_{1}^{*}\\ \tau_{2}(s,u)&\textrm{if }(s,u)\in S_{2}\times\Sigma_{2}^{*}\\ \{(s_{2},u)\}&\textrm{if }(s,u)\textrm{ is a final output configuration of }M_% {1}\\ \varnothing&\textrm{otherwise.}\end{array}\right.$ Again, since both $\tau_{1}$ and $\tau_{2}$ are finite, so is $\tau$, and thus $M$ welldefined. In addition, $\operatorname{RT}_{M}=\operatorname{RT}_{{M_{2}}}\circ\operatorname{RT}_{{M_{1% }}}$.
A family $\mathscr{F}$ of languages is said to be closed under rational transduction if for every $L\in\mathscr{F}$, and any rational transducer $M$, we have $\operatorname{RT}_{M}(L)\in\mathscr{F}$. The three properties above show that if $\mathscr{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).
Mathematics Subject Classification
03D05 no label found68Q45 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections