1
$\begingroup$

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!

Improve this question
$\endgroup$
4
  • $\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, 2014 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, 2014 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, 2014 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, 2014 at 20:48

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ FYI: Classes closed under finite state transductions are called "full trio" or "cone". $\endgroup$
    – Hendrik Jan
    Aug 5, 2014 at 11:19
3
$\begingroup$

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?

Improve this answer
$\endgroup$
1
  • $\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, 2014 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.