Σ* to at most one Γ*, are called rational functions. Finite-state transducers are often used for phonological and morphological analysis in natural language processing research and applications. Pioneers in this field include Ronald Kaplan, Lauri Karttunen, Martin Kay and Kimmo Koskenniemi. 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). Formal construction Formally, a finite transducer T is a 6-tuple () such that: is a finite set, the set of states; is a finite set, called the input alphabet; is a finite set, called the output alphabet; is a subset of , the set of initial states; is a subset of , the set of final states; and (where ε is the empty string) is the transition relation. We can view (Q, δ) as a labeled directed graph, known as the transition graph of T: the set of vertices is Q, and means that there is a labeled edge going from vertex q to vertex r. We also say that a is the input label and b the output label of that edge. NOTE: This definition of finite transducer is also called letter transducer (Roche and Schabes 1997); alternative definitions are possible, but can all be converted into transducers following this one. Define the extended transition relation as the smallest set such that: ; for all ; and whenever and then . The extended transition relation is essentially the reflexive transitive closure of the transition graph that has been augmented to take edge labels into account. The elements of are known as paths. The edge labels of a path are obtained by concatenating the edge labels of its constituent transitions in order. The behavior of the transducer T is the rational relation [T] defined as follows: if and only if there exists and such that . This is to say that T transduces a string into a string if there exists a path from an initial state to a final state whose input label is x and whose output label is y. Weighted automata Finite State Transducers can be weighted, where each transition is labelled with a weight in addition to the input and output labels. A Weighted Finite State Transducer (WFST) over a set K of weights can be defined similarly to an unweighted one as an