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:
“Plot, rules, nor even poetry, are not half so great beauties in tragedy or comedy as a just imitation of nature, of character, of the passions and their operations in diversified situations.”
—Horace Walpole (1717–1797)
“Put shortly, these are the two views, then. One, that man is intrinsically good, spoilt by circumstance; and the other that he is intrinsically limited, but disciplined by order and tradition to something fairly decent. To the one party man’s nature is like a well, to the other like a bucket. The view which regards him like a well, a reservoir full of possibilities, I call the romantic; the one which regards him as a very finite and fixed creature, I call the classical.”
—Thomas Ernest Hulme (1883–1917)
“The essence of the modern state is that the universal be bound up with the complete freedom of its particular members and with private well-being, that thus the interests of family and civil society must concentrate themselves on the state.... It is only when both these moments subsist in their strength that the state can be regarded as articulated and genuinely organized.”
—Georg Wilhelm Friedrich Hegel (1770–1831)