For a deterministic finite automaton (DFA), some output tasks are easy when done in one direction, but difficult (or impossible?) when done in the reverse direction. Let's take a simple example of outputting a word lower-case, or upper-case, depending on a control sequence included in the input. So the task

  • l:aNNa should become anna
  • u:aNNa should become ANNA

(where aNNa could be an arbitrary long word) seems to be quite easy for a DFA with output. The task in the reverse direction

  • aNNa:l should become anna
  • aNNa:u should become ANNA

however seems to be impossible for a DFA with output, at least for the commonly encountered definitions of DFA with output. On the other hand, a nondeterministic finite automaton (NFA) with unique output has no problems doing a task in the reverse direction, if it can do it in one direction.

  1. Is the observation correct that a DFA with output can't do the task in the reverse direction, if it is forced to consume its input one symbol at a time?

  2. Would it be possible to relax the restrictions for DFA and NFA, such that a NFA (with unique output) would not gain any additional expressiveness from the relaxed restrictions, but the DFA with output (for the relaxed restrictions) would be able to match the expressiveness of a NFA with unique output?

  • $\begingroup$ This is a very interesting question and there is a lot to say about it. I will try to provide a detailed answer as soon as I find the time to do it. $\endgroup$
    – J.-E. Pin
    May 12 '15 at 4:44
  • $\begingroup$ @J.-E.Pin My "real" question was in terms of rational subsets of $\Sigma^*\times\Sigma^*$ (modeling NDA) vs. recognizable subsets of $\Sigma^*\times\Sigma^*$ (modeling DFA). After having noticed that I can specify rational subsets of $\Sigma^*\times\Sigma^*$ by suitable regular expressions, and that these subsets correspond to the output of NFA, I wondered whether these are computable by DFA, if suitably restricted. $\endgroup$ May 12 '15 at 6:48
  • $\begingroup$ @J.-E.Pin I tried my luck now and wrote an answer myself. The bimachine seems to be the appropriate relaxation of the restrictions of DFA with output (which still can be seen as a machine with only finitely many states) to match the expressiveness of NFA with unique output. As a weaker more practical alternative, I also mention plurisubsequential functions, which seem to correspond to one prescan of the input, followed by the scan of the input which produces the actual output. $\endgroup$ Jun 7 '15 at 14:15
  • $\begingroup$ I apologize for not having written up my promised answer yet, but fortunately your own answer is a very good one. $\endgroup$
    – J.-E. Pin
    Jun 7 '15 at 14:41

An interesting definition can be found in an old survey article by J. Berstel and J. Sakarovitch

A plurisubsequential function is a finite union of subsequential functions having pairwise disjoint domains. A subsequential function is a function realized by a gsm equipped with an additional partial output function $\rho$ defined on the states of the gsm. ...1

The finite union with pairwise disjoint domains covers cases like above, where more than one output makes sense, but we know only later which. An reasonable implementation could first scan the input once, determine the relevant subsequential function, and then compute that function by a second scan over the input.

The survey proves that addition of one is a plurisequential functions if the digits of the number are given in low-ending order, but not if the digits are given in big-endian order. So the observation from the question about the reverse direction is correct.

Interesting, J. Berstel also wrote a book which contains an answer to the question whether it is possible to relax the restrictions for DFA with output such that it matches expressiveness of NFA with unique output. From J. Berstel, Transductions and context-free languages Chapter IV, 5 Bimachines

Definition A bimachine $\mathfrak B = \langle Q, q_-, P, p_−, \gamma\rangle$ over $A$ and $B$ is composed of two finite sets of states $Q,P$, two initial states $q_− \in Q$, $p_− \in P$, of two partial next state functions $Q \times A \to Q$ and $A \times P \to P$ denoted by dots, and a partial output function $\gamma : Q \times A \times P \to B^∗$.

The output of such a machine is naturally partitioned into as many parts as the input has symbols, some of these parts can be empty. To compute the $i$-th part, $Q$ processes the first $i-1$ input symbols forward, $P$ processes the last $n-i-1$ input symbols backward, and $\gamma$ computes the output from the $i$-th input symbol $a$ and the current states $q$ and $p$ of $Q$ and $P$ as $\gamma(q,a,p)$.

A partial function is rational if and only if it is realized by a bimachine. Bimachines were introduced by Schützenberger in 1961. In 2006, J. Rhodes organized a P vs NP Workshop, and where Pedro V. Silva gave an introduction to bimachines.

A bimachine has only a finite number of states and is deterministic, but in general it needs $O(n)$ forward and backward scans over the input. The plurisubsequential functions (or slight extensions of this idea) are attractive, because they only need two forward scans over the input.

1 ... If a computation in the gsm ends in some state, then the word associated with that state by the function $\rho$ is concatenated at the end of the output, provided p is defined for this state. Otherwise, it indicates that the computation is unsuccessful, and therefore that the function realized by this transducer is undefined for the given input.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.