Q:

Can DFA with output (definition?) match expressiveness of NFA with unique output?

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.

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?
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?

A:

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.

