NationMaster - Encyclopedia: Finite state transducer

Contrast this with an ordinary finite state automaton, which has a single tape. 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 recognized. The class of languages generated by finite automata is known as the class of regular languages. In the theory of computation, a finite state machine (FSM) or finite state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. ... In mathematics, logic, and computer science, a formal language is a set of finite-length words (i. ... In the mathematical subfield of set theory, the indicator function, or characteristic function, is a function defined on a set X which is used to indicate membership of an element in a subset A of X. Remark. ... A regular language is a formal language (i. ...

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. In the theory of computation, a nondeterministic algorithm is a hypothetical algorithm where computation can branch, choosing among different execution paths in a way that does not depend only on the input and current execution state. ... In mathematics, a finitary relation is defined by one of the formal definitions given below. ...

Finite State Transducers are typically used for morphological analysis in natural language processing research and applications. Morphology is a subdiscipline of linguistics that studies word structure. ... Natural language processing (NLP) is a subfield of artificial intelligence and linguistics. ...

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

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 (Sigmacup{epsilon}) times (Gammacup{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)indelta$ 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. In mathematics, a set is called finite if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ... In various branches of mathematics and computer science, strings are sequences of various simple objects (symbols, tokens, characters, etc. ... This article just presents the basic definitions. ...

Define the extended transition relation $δ *$ as the smallest set such that:

$deltasubseteqdelta^*$ ;
$(q,epsilon,epsilon,q)indelta^*$ for all $qin 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. In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. For any relation R the transitive closure of R always exists. ...

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 $xinSigma^*$ into a string $yinGamma^*$ if there exists a path from an initial state to a final state whose input label is x and whose output label is y. It has been suggested that this article or section be merged with Logical biconditional. ...

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

Concatenation. Given transducers T and S, there exists a transducer $Tcdot S$ such that $wx[Tcdot 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).

Note that there is no notion of intersection of transducers. Instead, there is an operation of composition that is specific to transducers and whose construction is similar to that of intersection of automata. Composition is defined as follows: In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ... In mathematical logic and computer science, the Kleene star (or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. ... The term intersection can mean: a road junction, where two roads intersect each other, such as a roundabout intersection; in mathematics, the set in which two or more other sets intersect each other; see intersection (set theory); a movie; see Intersection (movie). ...

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[Tcirc S]z$ if and only if there exists a string $yinGamma^*$ such that $x [T] y$ and $y [S] z$ .

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.

The word decidable has formal meaning in computability theory, the theory of formal languages, and mathematical logic. ... Undecidable has more than one meaning: In mathematical logic: A decision problem is undecidable if there is no known algorithm that decides it. ...

Contents

Formal construction GA_googleFillSlot("encyclopedia_square");

Operations on finite state transducers

Additional properties of finite state transducers

See also

Further reading

Formal construction