Is string matching and replacement, as an operation on strings or on formal languages, considered in formal languages?

  1. For example, the family of regular languages, or the family of context free languages, ..., are closed under certain string operations.

    I would wonder if these families or some others may be closed under string matching and replacement?

  2. Are string matching and replacement equivalent to some combination of other string operations?
  3. Or is matching and replacement considered in formal languages in some other ways?

Thanks and regards!

  • $\begingroup$ To clarify. If I have a string abbb and replace ab with ba, do I end up with babb or bbba? $\endgroup$ – Karolis Juodelė Aug 4 '14 at 13:23
  • $\begingroup$ As an operation on strings, either is fine, As an operation on languages, it seems natural to me that matching and replacement can be applied arbitrarily many times. $\endgroup$ – Tim Aug 4 '14 at 13:31
  • $\begingroup$ If replacing is not iterated, I suspect that everything is closed under it. If replacing is iterated, regular bcbcbc can be easily turned into bbbccc and context free aaabcbcbc can be turned into context sensitive aaabbbccc. If several rewriting rules can be iterated, all RE languages can be generated, but if it's just one, then I'm not sure. $\endgroup$ – Karolis Juodelė Aug 4 '14 at 14:07
  • $\begingroup$ Technically, it seems like "string matching" is exactly the problem solved by automata. Replacement seems like a special case of the problem transducers solve, i.e., reading input and emitting output. $\endgroup$ – Patrick87 Aug 4 '14 at 20:48

Match & replace is a special case of rational transduction, a quite powerful class of string mappings with a number of nice properties.

The classes of regular, context-free and recursive enumerable languages are all closed against rational transduction (source), so this carries over to match & replace.

It does not seem as if the necessary elementary operations had a representation in formal language theory.

| cite | improve this answer | |
  • 1
    $\begingroup$ FYI: Classes closed under finite state transductions are called "full trio" or "cone". $\endgroup$ – Hendrik Jan Aug 5 '14 at 11:19

Well, basically the application of a production by a grammar is find & replace. So string matching and replacement is part of type-0 grammars, at the heart of formal languages. Iterated replacement is computing.

Or is that too simple?

| cite | improve this answer | |
  • $\begingroup$ I have never viewed the act of applying a grammar rule as search & replace. Maybe because, to me, a grammar is a declarative object whereas search & replace is an operational object (a procedure/algorithm). $\endgroup$ – Raphael Aug 4 '14 at 23:18

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.