rational transducer


A rational transducer is a generalizationPlanetmathPlanetmath of a generalized sequential machine (gsm). Recall that a gsm M is a quadruple (S,Σ,Δ,τ) where S is a finite setMathworldPlanetmath of states, Σ and Δ are the input and output alphabets respectively, and τ 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 componentsMathworldPlanetmath above, except that the transition function τ 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,Σ,Δ,τ) where S,Σ,Δ are defined just as those in a gsm, except that the transition function τ has domain a finite subset of S×Σ* such that τ(s,u) is finite for each (s,u)dom(τ). One can think of τ as a finite subset of S×Σ*×S×Δ*, or equivalently a finite relationMathworldPlanetmathPlanetmathPlanetmath between S×Σ* and S×Δ*.

Like a gsm, a rational transducer can be turned into a languagePlanetmathPlanetmath acceptor by fixing an initial state s0S and a non-empty set F of finite states FS. In this case, a rational transducer turns into a 6-tuple (S,Σ,Δ,τ,s0,F). An input configurationMathworldPlanetmath (s0,u) is said to be initial, and an output configuration (t,v) is said to be final if tF. The language accepted by a rational transducer M is defined as the set

L(M):={uΣ*τ(s0,u) contains an final output configuration.}.

Rational Transductions

Additionally, like a gsm, a rational transducer can be made into a language translator. The initial state s0 and the set F of final states are needed. Given a rational transducer M, for every input word u, let

RTM(u):={vΔ*(t,v)τ(s0,u) is a final output configuration.}.

Thus, RTM is a functionMathworldPlanetmath from Σ* to P(Δ*), 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 Σ,


In this way, RTM may be thought of as a language translator.

As with GSM mappings, one can define the inverseMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath of a rational transduction, given a rational transduction RTM:

RTM-1(v):={uvRTM(u)} and RTM-1(L):={RTM-1(v)vL}.

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 homomorphismMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath, as well as intersectionDlmfMathworldPlanetmathPlanetmath with any regular language, is a rational transduction.

  • The inverse of a rational transduction is a transduction. Given any rational transducer M=(S,Σ,Δ,τ,s0,F), define a rational transducer M=(S,Δ,Σ,τ,t0,F) as follws: S=S{t0} (where denotes disjoint unionMathworldPlanetmathPlanetmath), F={s0}, and τS×Δ*×S×Σ* is given by

    τ(t,v)={{(s,v)(s,v) is a final output configuration of M}if t=t0{(s,u)(t,v)τ(s,u)}otherwise.

    As τ is finite, so is τ, so that M is well-defined. In addition, RTM=RTM-1. As a corollary, the inverse homomorphism is a rational transduction.

  • The compositionMathworldPlanetmath of two rational transductions is a rational transduction. To see this, suppose M1=(S1,Σ1,Δ1,τ1,s1,F1) and M2=(S2,Σ2,Δ2,τ2,s2,F2) are two rational transducers such that Δ1Σ2. Define M=(S,Σ1,Δ2,τ,s1,F2) as follows: S=S1S2, and τS×Σ1*×S×Δ2* is given by

    τ(s,u)={τ1(s,u)if (s,u)S1×Σ1*τ2(s,u)if (s,u)S2×Σ2*{(s2,u)}if (s,u) is a final output configuration of M1otherwise.

    Again, since both τ1 and τ2 are finite, so is τ, and thus M well-defined. In addition, RTM=RTM2RTM1.

A family of languages is said to be closed under rational transduction if for every L, and any rational transducer M, we have RTM(L). The three properties above show that if is closed under rational transduction, it is a cone. The converseMathworldPlanetmath 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.


  • 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 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