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.

  • $\begingroup$ This operation can be implemented by three finite transducers that are arranged in a configuration c(reverse(b(reverse(a(x))))), where reverse 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:55
  • $\begingroup$ Also, since reversing the input requires O(n) memory I wonder, is this model of c(r(b(r(a(x))))) as powerful as a pushdown automaton? $\endgroup$ – orlp May 6 '17 at 11:03
  • $\begingroup$ @orlp Actually two-way finite state transducers, which can walk up-and-down the input tape are a known model of computation. $\endgroup$ – Hendrik Jan May 6 '17 at 11:44
  • $\begingroup$ @orlp By "pushdown automaton" you mean a transducer with an additional stack as storage? If I am not mistaken the domain (input strings of succesful computations) of a finite state transducers is regular, whereas a pda can accept non-regular languages. groeten $\endgroup$ – Hendrik Jan May 6 '17 at 11:48

Your Answer

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

Browse other questions tagged or ask your own question.