# 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 non-empty set $F$ of finite states $F\subseteq S$. In this case, a rational transducer turns into a 6-tuple $(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\lx@stackrel{{\scriptstyle\cdot}}{{\cup}}\{t_{0}\}$ (where $\lx@stackrel{{\scriptstyle\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 well-defined. 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}\lx@stackrel{{\scriptstyle\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$ well-defined. 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).
Title rational transducer RationalTransducer 2013-03-22 18:59:29 2013-03-22 18:59:29 CWoo (3771) CWoo (3771) 12 CWoo (3771) Definition msc 03D05 msc 68Q45 GeneralizedSequentialMachine rational transduction