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 non-empty set $F$ of finite states $F\subseteq S$. In this case, a rational transducer turns into a 6-tuple $(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

  As $\tau$ is finite, so is ${\tau }^{\prime }$, so that $M^{\prime }$ is well-defined. 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

  Again, since both ${\tau }_1$ and ${\tau }_2$ are finite, so is $\tau$, and thus $M$ well-defined. In addition, ${\mathrm{RT}}_M={\mathrm{RT}}_{M_2}\circ {\mathrm{RT}}_{M_1}$.

A family $ℱ$ of languages is said to be closed under rational transduction if for every $L\in ℱ$, and any rational transducer $M$, we have ${\mathrm{RT}}_M(L)\in ℱ$. The three properties above show that if $ℱ$ 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.

Title	rational transducer
Canonical name	RationalTransducer
Date of creation	2013-03-22 18:59:29
Last modified on	2013-03-22 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