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)))))
, wherereverse
reverses 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