Re:  the first part, that&#x27;s fair.<p>&gt; Cox&#x27;s formulation very explicitly provides an implementation of the NFA algorithm that uses constant resources (with respect to the input).<p>Not constant, <i>bounded</i>.  Theoretical CS doesn&#x27;t care about the difference, but in practice it matters a lot.  People provision hardware for the median case (really more like the 90th percentile), because provisioning for the worst case is really expensive.  When something is bounded, but not constant, there exists the possibility of a resource exhaustion attack.<p>&gt; It&#x27;s exponential because it requires counting. You don&#x27;t actually know when you&#x27;ve seen the initial zero, since you can see any number of 0s or 1s before it, and exactly N number of 0s or 1s after it.<p>I misinterpreted this one, because the convention I&#x27;m used to is that the expression is expected to match the entire input.  I prefer this convention for its elegance, but it&#x27;s much less common in practice than the Perl-like convention where you need to specify that you want that behavior.<p>I also didn&#x27;t sufficiently reconsider the expression when I realized this:  the terminal anchor is quite relevant, but I forgot it was there.  In reality you&#x27;re correct about this with the convention you are using.