&gt; Aside: out of curiosity it would have been interesting to see how a Thompson NFA[1] would have dealt with this.<p>It wouldn&#x27;t have dealt with it right? NFAs and DFAs are equivalent and them being actually regular means they can&#x27;t do things like count parentheses.