# 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. – David Richerby 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. – David Richerby 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

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.