Great article! Ah someone else also read it through...

"Matching of regular expressions is NP-complete. As such you can solve any other NP problem using regular expressions."

Would love to see that be the mechanism of that proof.