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

[geekphilosopher]

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.

[jbert]

Thanks. I have a limited CS background (some register machines, recursive and primitive recursive functions) and this gives me quite a few pointers to picking up some more.