Many programming languages support a "regular expression substitution" operation: if r is a regular expression and s, t are strings, sub(s, r, t) finds the first substring of s that matches the regexp r and replaces it with t.
Can this operation always be represented as a finite-state transduction? In particular, are we guaranteed that for each r, t, there exists a finite-state transducer $T$ that implements the function s $\mapsto$ sub(s, r, t)? Can it be done with a deterministic finite-state transducer? If not, can it be done with a non-deterministic finite-state transducer?
Here's an example of a case that seems non-obvious to me. Consider the regexp 00(00)*11, e.g., the operation sub(s, "00(00)*11", "2"). If we imagine trying to build a finite-state transducer for this operation, it seems like once it has seen 00 on the input, it has to keep reading 00's until it sees a 1 and not output anything until then (since it doesn't know whether this block will be of the form 0000...0011 or 0000..0010). If it sees 0000..0010, then at that point has to emit all of the saved-up 00's. But how does it keep track of how many to emit? Finite-state machines can't count, so I can't see how to achieve this.
c(reverse(b(reverse(a(x))))), wherereversereverses the input. The first transducer inserts start and end markers of possible matches, the second cleans those up and finds the actual start/end marker of the match, and the third one does the replacement. $\endgroup$ – orlp May 6 '17 at 10:55c(r(b(r(a(x)))))as powerful as a pushdown automaton? $\endgroup$ – orlp May 6 '17 at 11:03