Is string matching and replacement, as an operation on strings or on formal languages, considered in formal languages?
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?
- Are string matching and replacement equivalent to some combination of other string operations?
- Or is matching and replacement considered in formal languages in some other ways?
Thanks and regards!
abbb
and replaceab
withba
, do I end up withbabb
orbbba
? $\endgroup$bcbcbc
can be easily turned intobbbccc
and context freeaaabcbcbc
can be turned into context sensitiveaaabbbccc
. 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$