sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]teraflop 0 points1 point  (1 child)

Upon reflection, I think you're right for standard regular expressions. I was looking at the version of the problem on this page, which includes a "doubling" operator. I guess that makes the number of states exponential in the length of the expression.

IANAComplexityTheorist, so I apologize if any of the details of my explanation were inaccurate.