Fun with automata: Constructing the minimal DFA for a given NFA is PSPACE-hard. There are families of NFAs with <i>n</i> states so that the powerset automaton has <i>2^n</i> states, but the minimal DFA has 1 state. Example: Let Σ={a,b} be the alphabet, Q={q1, ..., qn} be the states. q1 has a self-loop with both a and b and a transition to q2 with a. q2 to q(n-1) have transitions with a and b to the next state (q2 -&gt; q3 etc). qn has no transitions. q1 and qn are the only accepting states. This is basically the &quot;n-th-to-last letter was an a&quot; automaton with the modification that the starting state is accepting.