Transducer (computer science)

In theoretical computer science, a transducer is a special finite automaton . It is characterized by the fact that, in contrast to an acceptor, it generates an output. It converts (translates) a source language into a target language. Since the formal properties of these languages ​​can vary, a distinction is made between various sub-types, which are described in more detail below.

Finite transducer

Finite transducers are finite automata which, unlike acceptors, also have an output function. In the classic definition, this function is linked to the transitions and the end states of the automaton. Figure 1 shows an alphabet- based transducer that replaces each occurrence of in an input string with a single occurrence in the output. For example, for input is output. In state 1, for example, the transducer can read an a, output an x ​​for it and go to state 2. State 2 is not a final state, since a b must now be read. Since the length to be replaced and the replaced one in the example are of different lengths, the empty word is output when reading b when changing from 2 to 0 . ${\displaystyle \{a,b,c,d,e,x\}}$ ${\displaystyle ab}$ ${\displaystyle x}$ ${\displaystyle acabd}$ ${\displaystyle acxd}$ ${\displaystyle \varepsilon }$

Fig. 1: Transductor that replaces ab by x

Fig. 2: Nondeterministic transducer

Fig. 3: Deterministic version of the transducer from Fig. 2

Fig. 4: Non-determinable transducer

Mathematical definition

A transducer is a 7- tuple , where: ${\displaystyle (Q,\Sigma ,\Gamma ,q_{0},\delta ,F,\omega )}$

• ${\displaystyle Q}$ is a finite set of states,
• ${\displaystyle \Sigma }$is the input alphabet (a finite, non-empty set of symbols),
• ${\displaystyle \Gamma }$is the output alphabet (a finite, non-empty set of symbols),
• ${\displaystyle q_{0}\in Q}$is the initial state and one element from , ${\displaystyle Q}$
• ${\displaystyle \delta }$is the state transition function , ${\displaystyle \delta \colon Q\times \Sigma \cup \{\varepsilon \}\to 2^{Q}}$
• ${\displaystyle F}$is a finite set of final states ( ), ${\displaystyle F\subseteq Q}$
• ${\displaystyle \omega }$is the output function . ${\displaystyle \omega \colon Q\times \Sigma \cup \{\varepsilon \}\times Q\to \Gamma ^{*}}$

The transition function is that of a nondeterministic finite transducer, i.e. H. When reading a symbol a in state q, the transducer can in principle transition into several subsequent states. If, on the other hand , the transducer is deterministic , the transition function can be defined as follows: ${\displaystyle \delta }$

${\displaystyle \delta \colon Q\times \Sigma \to Q}$.

The output function is simplified in the deterministic case . ${\displaystyle \omega \colon Q\times \Sigma \to \Gamma ^{*}}$

Often transition and output function are also to a transition relation with summarized. ${\displaystyle \Delta }$ ${\displaystyle \Delta \subseteq Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma ^{*}\times Q}$

Algebraic Operations

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

• Concatenation : If and are transducers, then there is also a transductor. ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}\cdot T_{2}}$
• Union
• Star and plus shell formation
• reversal
• Inversion: interchanging the input and output band.
• composition

Only acyclic transducers or those that have no : x or x: transitions are closed under section . ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$

Transductors under:

• Complementation
• difference

There are also some optimization operations for transducers:

• Removal of : -transitions ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$
• Determination of the input band of the transducer. Fig. 3 shows the deterministic variant of the transducer from Fig. 2 (it should be noted that this transductor is not deterministic in the strict sense due to its epsilon transitions. See sub-sequential transducers). However, not all transducers, not even those that realize a function, can be determined. Fig. 4 shows a non-determinisable transducer. This distinguishes finite transducers from finite automata and has consequences for the decidability of the equivalence problem (see below) ${\displaystyle \Sigma ^{*}\to \Gamma ^{*}}$
• A sub-class of transducers allows equivalent minimal variants.
• Pushing : Moving output symbols as far as possible towards the start state. A clear normal form can be established through pushing in connection with determination .

Corresponding language class

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

Extensions

P-subsequent transducers

The conversion of a transductor into a -subsequential transducer is called determinization . The outputs are delayed and output at the end states using an additional final output function, which corresponds to the maximum number of outputs. Should be, one speaks of a sequential transducer. A sequential transducer, in which all states are also end states, is also called subsequential . All acyclic transducers can be converted into equivalent (in the sense of the implemented string function) -subsequential transducers. With a cyclic transducer, the determinability can be determined with the help of the " Twins Property ". ${\displaystyle p}$ ${\displaystyle \varphi }$ ${\displaystyle p}$ ${\displaystyle p=1}$ ${\displaystyle p}$

Mathematical definition

A -subsequential transducer is an 8-tuple , where: ${\displaystyle p}$ ${\displaystyle (Q,\Sigma ,\Gamma ,q_{0},\delta ,F,\omega ,\varphi )}$

• ${\displaystyle Q}$ is a finite set of states,
• ${\displaystyle \Sigma }$is the input alphabet (a finite, non-empty set of symbols),
• ${\displaystyle \Gamma }$is the output alphabet (a finite, non-empty set of symbols),
• ${\displaystyle q_{0}\in Q}$ is the initial state,
• ${\displaystyle \delta }$is the state transition function , ${\displaystyle \delta \colon Q\times \Sigma \to Q}$
• ${\displaystyle F\subseteq Q}$ is a finite set of final states,
• ${\displaystyle \omega }$is the output function , ${\displaystyle \omega \colon Q\times \Sigma \to \Gamma ^{*}}$
• ${\displaystyle \varphi }$is the final output function . ${\displaystyle \varphi \colon F\to {(\Gamma ^{*})}^{p}}$

The final output function outputs up to different strings at the final states, where is the finite number of ambiguities of a transducer . ${\displaystyle \varphi }$ ${\displaystyle p}$ ${\displaystyle p}$

One algorithm for determination is that of Mohri .

Use of weights

A weighted finite transducer is a transducer that has been expanded by a weight function that assigns values ​​to the transitions. These values ​​can come from any half-ring . ${\displaystyle \mathbb {K} }$

If, as above, the transition and output functions and the weighting function are combined to form a relation, a weighted transducer over a half-ring is an 8-tuple , where ${\displaystyle \mathbb {K} }$ ${\displaystyle (Q,\Sigma ,\Gamma ,I,\Delta ,F,\lambda ,\rho )}$

• ${\displaystyle Q,\Sigma ,\Gamma ,F}$ as above,
• ${\displaystyle I\subseteq Q}$ is a set of initial states
• ${\displaystyle \Delta }$is the relation , ${\displaystyle \Delta \colon Q\times (\Sigma \cup \{\varepsilon \})\times (\Gamma \cup \{\varepsilon \})\times \mathbb {K} \times Q}$
• ${\displaystyle \lambda }$is the weight function that assigns weights to the initial states, ${\displaystyle \lambda \colon I\to \mathbb {K} }$
• ${\displaystyle \rho }$is the weight function that assigns weights to the end states. ${\displaystyle \rho \colon F\to \mathbb {K} }$

The weights can be used, for example, in speech synthesis to offer different pronunciation options for an input character, which are differently probable. The probabilities can be determined by machine learning , for example .

Applications

• Morphological analysis
• Robust syntactic analysis
• Data compression
• Coding

Basement transducer

A basement transducer is an LR parser for a given context-free grammar , i.e. a basement automaton that generates an output.

See also

• Acceptor
• Compiler
• Basement machine
• Parser