Finite state transducer: Information from Answers.com

A finite-state transducer (FST) is a finite state machine with two tapes: an input tape and an output tape. This contrasts with an ordinary finite state automaton (or finite state acceptor), which has a single tape.

1 Overview
2 Formal construction
3 Operations on finite state transducers
4 Additional properties of finite state transducers
5 See also
6 Notes
7 Further reading

Overview

An automaton can be said to recognize a string if we view the content of its tape as input. In other words, the automaton computes a function that maps strings into the set {0,1}. Alternatively, we can say that an automaton generates strings, which means viewing its tape as an output tape. On this view, the automaton generates a formal language, which is a set of strings. The two views of automata are equivalent: the function that the automaton computes is precisely the indicator function of the set of strings it generates. The class of languages generated by finite automata is known as the class of regular languages.

The two tapes of a transducer are typically viewed as an input tape and an output tape. On this view, a transducer is said to transduce (i.e., translate) the contents of its input tape to its output tape, by accepting a string on its input tape and generating another string on its output tape. It may do so nondeterministically and it may produce more than one output for each input string. A transducer may also produce no output for a given input string, in which case it is said to reject the input. In general, a transducer computes a relation between two formal languages. The class of relations computed by finite state transducers is known as the class of rational relations.

Finite-state transducers are often used for morphological analysis in natural language processing research and applications.

Formal construction

Formally, a finite transducer T is a 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
$\delta \subseteq Q \times (\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\}) \times Q$ (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 $(q,a,b,r)\in\delta$ 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:

$\delta\subseteq\delta^*$ ;
$(q,\epsilon,\epsilon,q)\in\delta^*$ for all $q\in Q$ ; and
whenever $(q,x,y,r) \in \delta^*$ and $(r,a,b,s) \in \delta$ then $(q,xa,yb,s) \in \delta^*$ .

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: $x [T] y$ if and only if there exists $i \in I$ and $f \in F$ such that $(i,x,y,f) \in \delta^*$ . This is to say that T transduces a string $x\in\Sigma^*$ into a string $y\in\Gamma^*$ if there exists a path from an initial state to a final state whose input label is x and whose output label is y.

Finite State Transducers can be weighted, where each transition is labeled with a weight in addition to the input and output labels. This property makes FSTs very useful for machine learning applications. A Weighted Finite State Transducer (WFST) over a semiring K can be defined similarly to an unweighted one as an 8-tuple T=(Q, Σ, Γ, I, F, E, λ, ρ), where:

Q, Σ, Γ, I, F are defined as above;
$E \subseteq Q \times (\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\}) \times Q \times K$ (where ε is the empty string) is the finite set of transitions;
$\lambda: I \rightarrow K$ maps initial states to weights;
$\rho: F \rightarrow K$ maps final states to weights.

In order to make certain operations on WFSTs well-defined, the weights have to form a Semiring. Two typical semirings used in practice are Log and Tropical Semirings.

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 $T\cup S$ such that $x[T\cup S]y$ if and only if $x [T] y$ or $x [S] y$ .

Concatenation. Given transducers T and S, there exists a transducer $T\cdot S$ such that $wx[T\cdot S]yz$ if and only if $w [T] y$ and $x [S] z$ .

Kleene closure. Given a transducer T, there exists a transducer $T *$ with the following properties: (1) $ε[T *]ε$ ; (2) if $w [T *] y$ and $x [T] z$ then $w x [T *] y z$ ; and $x [T *] y$ 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) x[H]y if and only if x[T]y and x[S]y.

Composition. Given a transducer T on alphabets Σ and Γ and a transducer S on alphabets Γ and Δ, there exists a transducer $T \circ S$ on Σ and Δ such that $x[T \circ S]z$ if and only if there exists a string $y\in\Gamma^*$ such that $x [T] y$ and $y [S] z$ .

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 $T$ and $S$ , $(x,z)\in T\circ S$ when there exist some $y$ such that $(x,y)\in S$ and $(y,z)\in T$ .

One can also project out either tape of a transducer to obtain an automaton. There are two projection functions: $π 1$ preserves the input tape, and $π 2$ preserves the output tape. The first projection, $π 1$ is defined as follows:

Given a transducer T, there exists a finite automaton $π 1 T$ such that $π 1 T$ accepts x if and only if there exists a string y for which $x [T] y$ .

The second projection, $π 2$ is defined similarly.

Additional properties of finite state transducers

It is decidable whether the relation [T] of a transducer T is empty.

It is decidable whether there exists a string y such that x[T]y for a given string x.

It is undecidable whether two transducers are equivalent.

If one defines the alphabet of labels $L=(\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\})$ , finite state transducers are isomorphic to NDFA over the alphabet $L$ , and may therefore be determinized (turned into deterministic finite state machines over the alphabet $L=[(\Sigma\cup\{\epsilon\}) \times \Gamma] \cup [\Sigma \times (\Gamma\cup\{\epsilon\})]$ ) and subsequently minimized so that they have the minimum number of states.^{[citation needed]}

	Cone (formal languages)
	Morphological parsing
	Levenshtein automaton

	Using your own words write a maximum of 200 words on either a Mealy or a Moore Machine an adaptation of the finite state machine? Read answer...
	What is the definition of finite? Read answer...
	What is the meaning of transducer? Read answer...

	What is the state of steady state and unsteady state of finite element analysis?
	Application of acyclic finite state automata?
	What is Steady state in finite element analysis?

Finite state transducer

Contents

Overview

Formal construction

Operations on finite state transducers

Additional properties of finite state transducers

See also

Notes

Further reading