&gt; something like &#x2F;.+aaaaaaaaaa&#x2F;. In this case, the number of states the automaton could be in grows with the length of the input, until you hit the upper bound of &quot;all eleven states&quot;.<p>That&#x27;s just false for the NFA algorithm. I&#x27;m not sure where your confusion lay, unfortunately. There are no pathological cases for the NFA algorithm. Zero. Zip. Nada. It&#x27;s guaranteed O(mn) time. See Cox&#x27;s articles. They explain.<p>It is true of course that certain regexes run slower than others using the NFA algorithm, but this is because of constant factors, not because of any degradation in runtime complexity. When implementing the NFA algorithm, you can allocate all of the space you need upfront and then execute a search guaranteeing no additional allocation.<p>Offline DFAs do, however, have pathological cases where the number of states required is exponential. For example, `0[01]{n}$`, has an exponential number of states proportional to 2^n. (I think this is isomorphic to your example, assuming `a{11}$`.)<p>&gt; This adds unwarranted complexity if you&#x27;re doing ahead-of-time compilation. Perhaps the best approach there is to try to convert the regex to a DFA, but bound the number of states to some multiple of the number of NFA states. If you surpass this number, consult the requirements of the situation and either reject the expression or just use the NFA that was built in the process.<p>Sounds pretty complex to me. Certainly more complex and fiddly IMO than implementing a lazy DFA. (I&#x27;ve done both.)