Re^3: Negating Regexes: Tips, Tools, And Tricks Of The Trade

Cool. Thanks very much for this. I was picturing some kind of repeating search-and-replace regexp thing, using the string as a tape, emulating a turing machine. Of course, that's replacement as well but there are also probably a million other reasons why that wouldn't work.

Replies like this are one reason Why Perl Monks Works for Me.

Comment on Re^3: Negating Regexes: Tips, Tools, And Tricks Of The Trade

Replies are listed 'Best First'.
Re^4: Negating Regexes: Tips, Tools, And Tricks Of The Trade by Anonymous Monk on Dec 27, 2014 at 03:27 UTC
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.)	[reply]

Replies are listed 'Best First'.

Re^4: Negating Regexes: Tips, Tools, And Tricks Of The Trade
by Anonymous Monk on Dec 27, 2014 at 03:27 UTC

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.)

[reply]