NFA com número exponencial de estados quando deseminados

Como criar um exemplo de um DFA que possui $2^n$ estados em que o NFA equivalente possui $n$ estados. Obviamente, o conjunto de estados do DFA deve conter todos os subconjuntos do conjunto de estados da NFA, mas não sei como começar. Alguma sugestão para me colocar no caminho certo?

$L$$A$$n$$L$$n+1$$n$$a$$\epsilon$$A$ .

$L$$2^n$$S_1,S_2$$A$$w(S_1),w(S_2)$$S_1,S_2$$a \in S_1 \setminus S_2$$w = w(A-a)$$w(S_1)w \notin L$$w(S_2)w \in L$

este é um exercício no livro "Finite Automata", de Mark V. Lawson Universidade Heriot-Watt, Edimburgo, página 68:

$n \geq 1$$(0+1)^\ast 1(0+1)^{n−1}$$n+1$$2^n$ estados. Este exemplo mostra que, às vezes, é inevitável um aumento exponencial no número de estados, passando de um autômato não determinístico para um autômato determinante correspondente.

$2^n$$2^n$$\Omega(2^n)$ .

De "Complexidade da comunicação", de Kushilevitz e Nisan, no exercício 12.6:

$c$$L_c = \{ww\mid w \in \{0,1\}^c\}$ ."

$L_c$$O(c)$$\Omega(2^c)$

$A = \{a, b\}$$Q_n = \{0, 1, \ldots, n-1\}$${\cal A}_n = (Q_n, A, E_n, \{0\}, \{0\})$