{"id":812,"date":"2015-12-14T14:48:27","date_gmt":"2015-12-14T13:48:27","guid":{"rendered":"http:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=812"},"modified":"2017-02-03T06:49:15","modified_gmt":"2017-02-03T05:49:15","slug":"left-to-right-transducers","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20152016-2\/jezyki-automaty-i-obliczenia-2\/6-transducers\/left-to-right-transducers","title":{"rendered":"One-way transducers"},"content":{"rendered":"

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.<\/p>\n

 <\/p>\n

NFA with output<\/strong><\/p>\n

An\u00a0NFA with<\/em>\u00a0output\u00a0<\/em>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\u00a0functional\u00a0<\/em>if for every input word, there is exactly one output word (but possibly realised through several different accepting runs). Such an automaton is called\u00a0unambiguous\u00a0<\/em>if for every input word, it has a unique accepting run; this implies being functional.<\/p>\n

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”.
\n\"nfa<\/a><\/p>\n

Lookahead DFA with output<\/b><\/p>\n

Define a\u00a0lookahead DFA with output\u00a0<\/em>to be the following tuple:<\/p>\n

\u2022 an input alphabet \"\Sigma\";
\n\u2022 an output alphabet \"\Gamma\";
\n\u2022 a finite automaton, called the\u00a0lookahead automaton,\u00a0<\/em>which has\u00a0input alphabet \"\Sigma\" and\u00a0is deterministic from right to left;
\n\u2022 a set of control states \"Q\" \u00a0with a distinguished initial state \"q_0\";
\n\u2022 a transition function <\/p>\n

  <\/span>   <\/span>\"\[\delta : Q \times P \to Q \times \Gamma^*\]\"<\/p>\n

where \"P\" are the states of the lookahead automaton.<\/p>\n

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\u00a0on the\u00a0remaining input \"a_{i+1} \cdots a_{n}\" from right to left,\u00a0yielding a state\u00a0\"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.<\/p>\n

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”. \u00a0The automaton has only one control state, and uses a lookahead automaton whose states\u00a0partition the input words into four kinds: <\/p>\n

  <\/span>   <\/span>\"\[\epsilon \qquad \Sigma^*b \qquad a+a\Sigma^*a \qquad b\Sigma^*a\]\"<\/p>\n

Here is the picture of the automaton:<\/p>\n

\"dfalookahead\"<\/a><\/p>\n

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

Eilenberg bimachine<\/strong><\/p>\n

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:<\/p>\n

\u2022 an input alphabet \"\Sigma\";
\n\u2022 an output alphabet \"\Gamma\";
\n\u2022 a finite, called the\u00a0past<\/em>\u00a0automaton,\u00a0<\/em>which has\u00a0input alphabet \"\Sigma\" and\u00a0is deterministic\u00a0from left to right, i.e. in the usual sense of determinism;
\n\u2022\u00a0a finite, called the\u00a0future<\/em>\u00a0automaton,\u00a0<\/em>which has\u00a0input alphabet \"\Sigma\" and\u00a0is deterministic\u00a0from right to left;
\n\u2022 an output function \u00a0<\/p>\n

  <\/span>   <\/span>\"\[out : P \times \Sigma \times Q \to \Gamma^*\]\"<\/p>\n

where \"P\" are the states of the past\u00a0automaton and \"Q\" are the states of the future automaton.<\/p>\n

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\u00a0\"i\" by the value of the function \"out\" on the triple consisting of:
\n\u2022 the state of the past automaton on the prefix up to but not including \"i\";
\n\u2022 the \"i\"-th letter;
\n\u2022 the state of the future automaton on the suffix from but not including \"i\".<\/p>\n

This definition is illustrated below:<\/p>\n

\"eilenberg\"<\/a><\/p>\n

Theorem.\u00a0<\/strong>The following models are equivalent, in terms of the functions from words to words that they define:
\n1. functional NFA with output;
\n2. unambiguous NFA with output;
\n3. lookahead DFA with output;
\n4. Eilenberg bimachines.<\/p>\n

Proof.\u00a0<\/strong><\/p>\n