Re:If you can... (Score 1)

Uhm, to me, that sounds like saying "eggs aren't fruit - they are white". "Regular expressions", in the traditional sense, describe regular languages. NP-completeness refers to a certain class of problems for which no "fast" solution is known. What I proved was that matching a regular expression against a string can be an NP-complete problem. And while the proof is based on the same property as why perl regexes aren't "regular" (the backreferencing), one doesn't follow from the other.

Up till 5.005, for instance, perl regexes couldn't match a balanced parenthesis string. However, the language consisting of balanced parenthesis strings, is recognized by a PDA. And it doesn't take super linear time to do the parsing.

Am I making any sense?

Abigail