Editing Finite-state transducer (section)

==Overview==
{{external media
| float  = right
| video1 = [https://www.youtube.com/watch?v=F_dTuHS6Wbk Finite State Transducers] // [[Karlsruhe Institute of Technology]], YouTube video
}}

An [[automaton]] can be said to ''recognize'' a string if we view the content of its tape as input.  In other words, the automaton computes a function that maps strings into the set {0,1}.  Alternatively, we can say that an automaton ''generates'' strings, which means viewing its tape as an output tape.  On this view, the automaton generates a [[formal language]], which is a set of strings.  The two views of automata are equivalent: the function that the automaton computes is precisely the [[indicator function]] of the set of strings it generates.  The class of languages generated by finite automata is known as the class of [[regular language]]s.

The two tapes of a transducer are typically viewed as an input tape and an output tape.  On this view, a transducer is said to ''transduce'' (i.e., translate) the contents of its input tape to its output tape, by accepting a string on its input tape and generating another string on its output tape.  It may do so [[Nondeterministic algorithm|nondeterministic]]ally and it may produce more than one output for each input string.  A transducer may also produce no output for a given input string, in which case it is said to ''reject'' the input.  In general, a transducer computes a [[relation (mathematics)|relation]] between two formal languages.

Each string-to-string finite-state transducer relates the input alphabet Σ to the output alphabet Γ. Relations ''R'' on Σ*×Γ* that can be implemented as finite-state transducers are called '''rational relations'''. Rational relations that are [[partial function]]s, i.e. that relate every input string from Σ* to at most one Γ*, are called '''rational functions'''.

Finite-state transducers are often used for [[phonology|phonological]] and [[morphology (linguistics)|morphological analysis]] in [[natural language processing]] research and applications. Pioneers in this field include [[Ronald Kaplan]], [[Lauri Karttunen]], [[Martin Kay]] and [[Kimmo Koskenniemi]].<ref>{{harvnb|Koskenniemi|1983}}</ref>{{primary source inline|date=August 2014}}
A common way of using transducers is in a so-called "cascade", where transducers for various operations are combined into a single transducer by repeated application of the composition operator (defined below).