0
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 4
    $\begingroup$ 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. $\endgroup$
    – David Richerby
    Commented Jun 1, 2014 at 20:48
  • $\begingroup$ 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? $\endgroup$
    – Tim
    Commented Jun 1, 2014 at 21:35
  • 1
    $\begingroup$ "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. $\endgroup$
    – David Richerby
    Commented Jun 1, 2014 at 21:43
  • $\begingroup$ Can a "finite state transduction" be equivalent to some combination of more usual operations? $\endgroup$
    – Tim
    Commented Jun 1, 2014 at 21:45
  • 2
    $\begingroup$ 1. Please take more care with your question, to state the question precisely. Provide all relevant information. In this case, if you had written "I understand what a finite-state transducer is, but what is a transduction?", that would have helped. 2. When people offer comments or it becomes evident that your question was unclear, please edit your question to improve it. Don't just drop answers in the comment thread. The question needs to stand on its own, without reading the comments. Comments exist only to help you improve the question. 3. One question per question, please. $\endgroup$
    – D.W. ♦
    Commented Jun 2, 2014 at 6:01

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ "The wikipedia article on FST ignores a very important basic fact on transductions." Feel free to fix it! $\endgroup$
    – David Richerby
    Commented Jun 1, 2014 at 22:07
  • 1
    $\begingroup$ @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. $\endgroup$
    – Hendrik Jan
    Commented Jun 1, 2014 at 22:24
  • 1
    $\begingroup$ I know that feeling... $\endgroup$
    – David Richerby
    Commented Jun 1, 2014 at 22:41
  • 1
    $\begingroup$ 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? $\endgroup$
    – Tim
    Commented Jun 2, 2014 at 1:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.