Finite State Transducer - Formal Construction

Formal Construction

Formally, a finite transducer T is a 6-tuple (Q, Σ, Γ, I, F, δ) such that:

• Q is a finite set, the set of states;
• Σ is a finite set, called the input alphabet;
• Γ is a finite set, called the output alphabet;
• I is a subset of Q, the set of initial states;
• F is a subset of Q, 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 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.