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


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

Is there anyone here with sufficient computer science skillz to answer the question whether it is possible to write a program which will take an arbitrary regexp and contruct another which will act as it's negation against all possible input strings?

I would imagine you'd have to restrict the definition of "regular expression" to something a little less rich than the full perl set (isn't there a compsci definition?).

Presumably if regexps form a turing complete language then the answer is no, because this sounds awfully like such a program would violate the the Halting Problem (but maybe not - I haven't thought about it in detail).