No voy a ser capaz de demostrar que hay un DFA con $2^i$ declara que reconoce a $S_i$: no es difícil demostrar que un afd que reconoce a $S^0=\{\epsilon\}$ debe tener un mínimo de $2$ estados, no $2^0=1$, y un afd que reconoce a $S_1=\{00,11\}$ requiere al menos $5$ estados, no $2^1=2$.
La primera mitad del problema debe depender del hecho de que no se $2^i$ palabras de longitud $i$$\Sigma^*$. Supongamos que $M$ es un DFA con menos de $2^i$ estados. Luego, por el principio del palomar hay un estado de $q$ $M$ y las palabras de $u,v\in\Sigma^*$, cada uno de longitud $i$, de tal manera que $u\ne v$, pero $M$ está en estado de $q$ después de la lectura de cualquiera de las $u$ o $v$. Desde $M$ reconoce $uu$, también debe reconocer $vu$, lo que no debe. Por lo tanto, $M$ debe tener al menos $2^i$ estados.
Añadido: Por la NFA que Marko sugerido en los comentarios que han estado inicial $q_0$, estados $q_{k,\ell}$$k,\ell\in\{1,\dots,2i\}$, y un estado de $q_f$. Usted tiene los siguientes transiciones.
$$\begin{align*}
q_0&\overset{0}\longrightarrow q_{1,1}\\
q_0&\overset{1}\longrightarrow q_{1+i,1}\\
q_{1,i}&\overset{1}\longrightarrow q_{1,1+i}\\
q_{1+i,i}&\overset{0}\longrightarrow q_{1+i,1+i}\\
\end{align*}$$
Para cada una de las $k\in\{2,\ldots,i\}$:
$$\begin{align*}
q_0&\overset{0,1}\longrightarrow q_{k,1}\\
q_{k,k-1}&\overset{0}\longrightarrow q_{k,k}\\
q_{k+i,k-1}&\overset{1}\longrightarrow q_{k+i,k}\\
q_{k,k+i-1}&\overset{1}\longrightarrow q_{k,k+i}\\
q_{k+i,k+i-1}&\overset{0}\longrightarrow q_{k+i,k+i}
\end{align*}$$
Para cada $k\in\{1,\ldots,2i\}$: $$q_{k,2i}\overset{0,1}\longrightarrow q_f$$
Para cada una de las $\langle k\in\{1,\ldots,2i\}$ $\ell\in\{1,\ldots,2i-1\}$ para que la transición de la $q_{k,\ell}$ $q_{k,\ell+1}$aún no ha sido definida: $$q_{k,\ell}\overset{0,1}\longrightarrow q_{k,\ell+1}$$
Y por último, $$q_f\overset{0,1}\longrightarrow q_f$$
Cada una de las $4i^2+2$ estados es un aceptor de estado. Creo que de $q_{k,\ell}$ como en la fila $k$ y la columna $\ell$ $2i\times 2i$ matriz de estados, con $q_0$ a la izquierda y $q_f$ a la derecha. La única caminos a través de la máquina son de $q_0$ a lo largo de una fila de a $q_f$. Si me las arreglé para mantener mi subíndices recta, si $k\in\{1,\ldots,i\}$, una palabra que se obtiene a través de la ruta a lo largo de la fila $k$ $q_f$fib ha $0$ en la posición $k$ $1$ en la posición $k+i$, y se obtiene a través de la ruta a lo largo de la fila $k+i$ $q_f$fib tiene un $1$ en la posición $k$ y un $0$ en la posición $k+i$.
Puede que tenga que pensar un poco, pero esta NFA acepta cada palabra de longitud de menos de $2i$: incluso si es de la forma $uv$ donde $|u|=i$, e $v$ es un buen segmento inicial de $v$, va a ser aceptado en la fila $i$ o de la fila $2i$, dependiendo de si su $i$-ésimo símbolo es $0$ o $1$, respectivamente. Por lo tanto, la NFA maneja correctamente cada palabra de longitud en la mayoría de las $2i$. Sin embargo, no acaba de hacer lo que queremos: rechaza las palabras de la forma $uv$ donde$u\in S_i$$|v|>0$.
Usted puede reparar esto mediante la adición de los estados $q_k$$k\in\{1,\ldots,2i\}$, con transiciones $q_k\overset{0,1}\longrightarrow q_{k+1}$$k\in\{0,\ldots,2i-1\}$$q_{2i}\overset{0,1}\longrightarrow q_f$. Esto le da un camino de longitud $2i+1$ $q_0$ $q_f$que acepta cualquier palabra de longitud mayor que $2i$.
El número total de estados que ahora es $4i^2+2i+2$, pero que aún así es un polinomio en a $i$, y uno de bajo grado en que, por lo menos de lo $2^i$ para suficientemente grande $i$. (Si mi apresurada cálculos son correctos, $i\ge 9$ es lo suficientemente grande.)
