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.
Read more about this topic: Finite State Transducer
Famous quotes containing the words operations, finite and/or state:
“It may seem strange that any road through such a wilderness should be passable, even in winter, when the snow is three or four feet deep, but at that season, wherever lumbering operations are actively carried on, teams are continually passing on the single track, and it becomes as smooth almost as a railway.”
—Henry David Thoreau (1817–1862)
“Sisters define their rivalry in terms of competition for the gold cup of parental love. It is never perceived as a cup which runneth over, rather a finite vessel from which the more one sister drinks, the less is left for the others.”
—Elizabeth Fishel (20th century)
“A state that denies its citizens their basic rights becomes a danger to its neighbors as well: internal arbitrary rule will be reflected in arbitrary external relations. The suppression of public opinion, the abolition of public competition for power and its public exercise opens the way for the state power to arm itself in any way it sees fit.... A state that does not hesitate to lie to its own people will not hesitate to lie to other states.”
—Václav Havel (b. 1936)