Finite state transducer

A transducer is a special finite state machine in theoretical computer science. It is characterized in that it produces an output, in contrast to an acceptor. He transferred ( translated) a source language to a target language. Since the formal properties of these languages ​​may vary, one distinguishes different subtypes, which are described in more detail below.

A finite transducer

Finite transducers are finite automata, which also have an output function, in contrast to the acceptors. This is linked to the classical definition of the transitions and the final states of the automaton. Figure 1 shows an alphabet based on the transducer, which in an input string replaces each occurrence of by a single in the output. For example, the input is output. In state 1, the transducer, for example, an a read, to spend on an x and go to state 2. Condition 2 is not a final state, since now a b must be read. As in the example to the Substitute and the drafts are of different lengths, output the empty word when reading b in the transition from 2 to 0.

Mathematical definition

A transducer is a 7- tuple, wherein:

  • Is a finite set of states,
  • Is the input alphabet ( a finite, non- empty set of symbols),
  • Is the output alphabet ( a finite, non- empty set of symbols),
  • Is in the initial state and an element
  • Is the state transition function,
  • Is a finite set of final states ()
  • Is the output function.

The transition function is that of a non-deterministic finite Transducer, ie the transducer can when reading a symbol a in state q in principle proceed in several sequelae. If the transducer, however, deterministic, can the transition function defined as follows:

.

The output function can be simplified to the non- deterministic case.

Often transition and output function are combined to form a transition relation with.

Algebraic operations

The set of finite transducers is closed under the following operations:

  • Concatenation: Are transducers and so is also a transducer.
  • Union
  • Star Plus and shell formation
  • Reversal
  • Inversion: swapping input and output tape.
  • Composition

Under section are only acyclic transducers or those that do not: x or x: have transitions completed.

Not yet completed transducers are as under:

  • Complementation
  • Difference

Furthermore, there are some optimization operations for transducers:

  • Distance from: transitions
  • Determinisierung of the input bands of the transducer. Figure 3 shows the deterministic variant of the transducer of Figure 2 (note that this transducer in the strict sense by its epsilon transitions is not deterministic. Subsequentielle See transducers ). However, not all transducers, not even those that realize a function, be deterministic Siert. Figure 4 shows a non determinisierbaren transducer. This differs finite transducers of finite automata and has consequences for the decidability of the equivalence problem ( see below)
  • A subclass of transducers allows equivalent minimal variations.
  • Pushing: moving of output symbols as far as possible towards the starting state. By pushing in conjunction with Determinisierung, a unique normal form are produced.

Corresponding language class

The corresponding to finite transducers language class includes the so-called regular relations. See also formal languages, the Chomsky hierarchy.

Extensions

- subsequentielle transducers

The transfer of a Transducer in a - subsequentiellen transducer is called Determinisierung. The expenditure will be delayed and output by an additional Endausgabefunktion to the final states, corresponds to the maximum number of issues. Should be, it is called a sequential transducer. A sequential transducer, in which all states are terminal states is also subsequentiell. Any acyclic transducers can be converted into equivalent transducers (in the sense of realized string function ) subsequentielle. In a cyclic transducer the determinability using the "Twins Property" can be determined.

Mathematical definition

A - subsequentieller transducer is an 8- tuple, wherein:

  • Is a finite set of states,
  • Is the input alphabet ( a finite, non- empty set of symbols),
  • Is the output alphabet ( a finite, non- empty set of symbols),
  • Is the initial state,
  • Is the state transition function,
  • Is a finite set of final states,
  • Is the output function,
  • Is the Endausgabefunktion.

The Endausgabefunktion outputs up to several strings to the final states, here is the finite number of ambiguities of a Transducer.

An algorithm for Determinisierung is from Mohri.

The use of weights

A weighted finite state transducer is a transducer, which was extended by a weight function that assigns values ​​to the transitions. These values ​​can be from any semiring.

Summarizing above transition and output function, plus the weight function for a Relation together, is a weighted transducer over a semiring is an 8- tuple, where

  • As above,
  • Is a set of initial states,
  • Is the relation,
  • Is a weight function that assigns the initial states weights
  • Is a weight function that assigns weights final states.

The weights can for example be used in the speech synthesis to offer different pronunciations for the input characters that are likely to vary. The probabilities can be determined, for example by machine learning.

Applications

  • Morphological Analysis
  • Robust parsing
  • Data compression
  • Coding

Kellertransduktor

A Kellertransduktor is a LR parser to a given context-free grammar, that is a push-down automaton, which produces an output.

Finite-state machine Empty string Nondeterministic algorithm Text segmentation Compiler
782334
de