Finite State Transducer - Operations On Finite State Transducers

Operations On Finite State Transducers

The following operations defined on finite automata also apply to finite transducers:

• Union. Given transducers T and S, there exists a transducer such that if and only if or .

• Concatenation. Given transducers T and S, there exists a transducer such that if and only if and .

• Kleene closure. Given a transducer T, there exists a transducer with the following properties: (1) ; (2) if and then ; and does not hold unless mandated by (1) or (2).

• Intersection. Given transducers T, S, the intersection of these transducers H has the property that (1) xy if and only if xy and xy.

• Composition. Given a transducer T on alphabets Σ and Γ and a transducer S on alphabets Γ and Δ, there exists a transducer on Σ and Δ such that if and only if there exists a string such that and . This operation extends to the weighted case.

This definition uses the same notation which is used in mathematics for relation composition. However, the conventional reading for relation composition is the other way around: given two relations and, when there exist some such that and .

• Projection to an automaton. There are two projection functions: preserves the input tape, and preserves the output tape. The first projection, is defined as follows:

• Given a transducer T, there exists a finite automaton such that accepts x if and only if there exists a string y for which .

The second projection, is defined similarly.

• Determinization. Given a transducer T, we want to build an equivalent transducer which has a unique initial state and such that no two transitions leaving any state share the same input label. The powerset construction can be extended to transducers, or even weighted transducers, but sometimes fails to halt; indeed, some non-deterministic transducers do not admit equivalent deterministic transducers. Characterizations of determinizable transducers have been proposed along with efficient algorithms to test them: they rely on the semiring used in the weighted case as well as a general property on the structure of the transducer (the twins property).

• Weight pushing for the weighted case.

• Minimization for the weighted case.

• Removal of epsilon-transitions.