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.
in reply to Re: Negating Regexes: Tips, Tools, And Tricks Of The Trade
in thread Negating Regexes: Tips, Tools, And Tricks Of The Trade