I think wolfgke&#x27;s point (different from mine, by the way) was that you need to consider each state in each transition list just to check if it&#x27;s in the set you&#x27;ve already seen.  If you&#x27;re in all states, and all of them transition to all states on an input, that&#x27;s quadratic:  you need to loop through n lists of n states just to check if you&#x27;ve already visited any of them.<p>Of course, I don&#x27;t think there&#x27;s an actual regular expression that would produce that automaton using Thompson&#x27;s algorithm.