0
$\begingroup$

I am wondering what generic example there is so that an NFA with $n$ states results into a DFA with $2^n$ states after the conversion by the subset construction. I know there is the example by Hopcroft et al. where the resulting DFA has $2^{n-1}$ states, reproduced here, but I am looking for a result with exactly $2^n$ states.

$\endgroup$
1