A rational transducer is a generalization of a generalized sequential machine (gsm). Recall that a gsm is a quadruple where is a finite set 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 components 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 is a quadruple where are defined just as those in a gsm, except that the transition function has domain a finite subset of such that is finite for each . One can think of as a finite subset of , or equivalently a finite relation between and .
Like a gsm, a rational transducer can be turned into a language acceptor by fixing an initial state and a non-empty set of finite states . In this case, a rational transducer turns into a 6-tuple . An input configuration is said to be initial, and an output configuration is said to be final if . The language accepted by a rational transducer is defined as the set
Additionally, like a gsm, a rational transducer can be made into a language translator. The initial state and the set of final states are needed. Given a rational transducer , for every input word , let
Thus, is a function from to , and is called the rational transduction (defined) for the rational transducer . The rational transduction for can be extended: for any language over the input alphabet ,
In this way, 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 :
Here are some examples of rational transductions
The inverse of a rational transduction is a transduction. Given any rational transducer , define a rational transducer as follws: (where denotes disjoint union), , and is given by
As is finite, so is , so that is well-defined. In addition, . As a corollary, the inverse homomorphism is a rational transduction.
The composition of two rational transductions is a rational transduction. To see this, suppose and are two rational transducers such that . Define as follows: , and is given by
Again, since both and are finite, so is , and thus well-defined. In addition, .
A family of languages is said to be closed under rational transduction if for every , and any rational transducer , we have . 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.
- 1 A. Salomaa Computation and Automata, Encyclopedia of Mathematics and Its Applications, Vol. 25. Cambridge (1985).
|Date of creation||2013-03-22 18:59:29|
|Last modified on||2013-03-22 18:59:29|
|Last modified by||CWoo (3771)|