One-way transducers

Mikołaj Bojańczyk

zajęcia / courses

On this page, we describe three different models of transducers, which describe the same kinds of functions. The idea is that the functions process the input from left to right, but have some kind of mechanism (lookahead, or maybe nondeterminism) to query the part of the input that has not been seen yet.

NFA with output

An NFA with output is a nondeterministic finite automaton over an input alphabet $\Sigma$ , where each transition is labelled by a possibly empty word over the output alphabet. When given an input word over the input alphabet, the automaton produces all those words over the output alphabet which can be found by taking an accepting run, and reading from left to right the words on the transitions. Such an automaton is called functional if for every input word, there is exactly one output word (but possibly realised through several different accepting runs). Such an automaton is called unambiguous if for every input word, it has a unique accepting run; this implies being functional.

Here is an example of such an NFA, which is unambiguous, and which realises the function “identity if the last letter is $a$ , otherwise erase the entire word”.

Lookahead DFA with output

Define a lookahead DFA with output to be the following tuple:

• an input alphabet $\Sigma$ ;
• an output alphabet $\Gamma$ ;
• a finite automaton, called the lookahead automaton, which has input alphabet $\Sigma$ and is deterministic from right to left;
• a set of control states $Q$ with a distinguished initial state $q_0$ ;
• a transition function

$\delta : Q \times P \to Q \times \Gamma^*$

where $P$ are the states of the lookahead automaton.

The behaviour of the automaton, when given an input word $a_1 \cdots a_n$ over the input alphabet, is as follows. The automaton begins before the first position in the initial state. Suppose that the automaton has already read the letters $a_1 \cdots a_i$ , and is in state $q$ . One runs the lookahead automaton on the remaining input $a_{i+1} \cdots a_{n}$ from right to left, yielding a state $p$ . To the pair $(q,p)$ the transition function is applied, yielding a new state and some output word. The output word is added to the output produced so far, and the automaton moves to the next letter in the new state.

Here is an example of a lookahead DFA with output which realises the function “identity if the last letter is $a$ , otherwise erase the entire word”. The automaton has only one control state, and uses a lookahead automaton whose states partition the input words into four kinds:

$\epsilon \qquad \Sigma^*b \qquad a+a\Sigma^*a \qquad b\Sigma^*a$

Here is the picture of the automaton:

In general, there might be a need to use control states, e.g. for the function “swap the first and last letter”.

Eilenberg bimachine

An Eilenberg bimachine is very similar to a lookahead DFA with output, only the definition is more symmetric. The machine consists of the following ingredients:

• an input alphabet $\Sigma$ ;
• an output alphabet $\Gamma$ ;
• a finite, called the past automaton, which has input alphabet $\Sigma$ and is deterministic from left to right, i.e. in the usual sense of determinism;
• a finite, called the future automaton, which has input alphabet $\Sigma$ and is deterministic from right to left;
• an output function

$out : P \times \Sigma \times Q \to \Gamma^*$

where $P$ are the states of the past automaton and $Q$ are the states of the future automaton.

The function defined by such a machine is as follows. When given a word over the input alphabet, the automaton replaces, in parallel, each position $i$ by the value of the function $out$ on the triple consisting of:
• the state of the past automaton on the prefix up to but not including $i$ ;
• the $i$ -th letter;
• the state of the future automaton on the suffix from but not including $i$ .

This definition is illustrated below:

Theorem. The following models are equivalent, in terms of the functions from words to words that they define:
1. functional NFA with output;
2. unambiguous NFA with output;
3. lookahead DFA with output;
4. Eilenberg bimachines.

Proof.

From 2 to 1. A special case.
From 1 to 3. A lookahead DFA with output can simulate a functional NFA with output in the same manner as above: it constructs some accepting run during its left to right pass.
From 3 to 2. An NFA can guess, in an unambiguous way, the run of the lookahead automaton.
From 2 to 4. An Eilenberg bimachine can simulate an unambiguous NFA with output: for every position, it computes the transition that is used in the unique run, and outputs the label of that transition.
From 4 to 2. An NFA can guess, in an unambiguous way, the runs of the past and future automaton in an Eilenberg bimachine.

$\Box$

zajęcia / courses

One-way transducers

One-way transducers

Leave a Reply