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


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

Regular expressions, at least using the computer science definition, are equivalent in expressive power to the regular langauges, hence their name. This means they can be defined in terms of a deterministic or non-deterministic finite automata. Adding a stack would give us a push-down automata, which can recognize context-free languages. Adding a second stack gives us something equivalent in power to a Turing machine.