# What does "finite state transduction" mean?

Wikipedia says, the regular languages are closed under

arbitrary finite state transductions, like quotient K / L with a regular language.

I wonder what kinds of operations "finite state transductions" are? Btw, It links to finite state transducer, an automaton. Thanks.

• Finite state transductions are operations performed by finite state transducers, which are described in the link from the phrase "finite state transductions" in the Wikipedia article. Pleaee ask a more specific question about the parts you didn't understand. Jun 1 '14 at 20:48
• Yes, I read. But there is no "transduction" mentioned in the Wikipedia article for finite state transducer. (1) did you mean that the operation of "a finite state transduction" is defined as, applying its operand string to a "finite state transducer", and then taking the output of the "finite state transducer" on the operand string as the return by the operation of "a finite state transduction"? (2) Will the operation of "a finite state transduction" be different for different finite state transducers?
– Tim
Jun 1 '14 at 21:35
• "On this view, a transducer is said to transduce"; "transduction" is the act of transducing. (1) Yes, and this is applied to whole languages: you start with a language $L$, feed every string of it to your transducer and the set of outputs you get is a new language. (2) Of course, just as the operation of "finite state acceptance" is different for different automata. Jun 1 '14 at 21:43
• Can a "finite state transduction" be equivalent to some combination of more usual operations?
– Tim
Jun 1 '14 at 21:45
– D.W.
Jun 2 '14 at 6:01

A finite state transducer is a machine model, much like a finite state automaton, but equipped with two tapes, one for input and one for output. Each specific finite state automaton defines a binary relation between input and output strings.

Your assumption is right: for each input string we look at computations that match that string and output the corresponding strings on the second tape. This process can be highly nondeterministic, as symbols can be deleted and inserted at will (when the automaton is programmed to do so). This definition is extended to languages: each transducers defines a binary relation on languages too.

Transducers can be found for a very broad class of tasks: homomorphisms, inverse homomorphisms, intersection or quotient with (a fixed) regular language. Finite state transducers are nice devices, e.g., they can be programmed to deleted every second $a$ in a string, but only for strings ending in a $b$.

The wikipedia article on FST ignores a very important basic fact on transductions. They happen to be equal to the class of operations built from homomorphisms, inverse homomorphisms and intersection with regular languages. Each family closed under these operations is called a trio, and such a class is then closed under all FST's. Examples are the family of regular languages and the family of context-free languages. So as a consequence, given a CFL, the language we obtain by erasing every second $a$ (for strings that end in a $b$) is again context-free.

• "The wikipedia article on FST ignores a very important basic fact on transductions." Feel free to fix it! Jun 1 '14 at 22:07
• @DavidRicherby Yes, I do have a wikipedia account. Wikipedia is written by a collective and sometimes a topic is just a bucket full of ideas thrown in by whoever, without any coherence. Sometimes I do not know where to start. Jun 1 '14 at 22:24
• I know that feeling... Jun 1 '14 at 22:41
• Thanks. David. "This process can be highly nondeterministic, as symbols can be deleted and inserted at will (when the automaton is programmed to do so)". (1) What do you mean by "symbols" that can be deleted and inserted at will? Do you mean the symbols in the input? (2) By " highly nondeterministic", do you mean different transducers have different state-transition functions and/or output functions, and therefore represent different transduction operations? For a given transducer, its state-transition and output functions are fixed, is the corresponding transduction operation deterministic?
– Tim
Jun 2 '14 at 1:02