http://www.perlmonks.org?node_id=1111445


in reply to Re^3: Negating Regexes: Tips, Tools, And Tricks Of The Trade
in thread Negating Regexes: Tips, Tools, And Tricks Of The Trade

Actually, it's entirely possible that what you describe is Turing-complete. The fact that a regex search and replace is one computing step doesn't place any particular limitation on the expressive power of your scheme. The same is true for an LR parser, which repeatedly uses a finite automaton to find handles. Finite automata can only parse regular languages, yet LR parsers can cope with any language parseable by a deterministic finite automaton, which is a strictly larger set. (For example, it includes the language of expressions with matching parentheses, which is not a regular language.)