Existencia de NFA para este lenguaje

Question

Me ha dado una tarea de encontrar (y demostrar) idioma $L$ en el alfabeto $\Sigma = \{a,b\}$ con todas las palabras de menos de $1000$ en longitud, para que cualquier DFA/NFA tener más de $10^{10}$ de los estados. Para la primera parte de la tarea, con DFA, he encontrado ese tipo de lenguaje (ver más abajo), pero no puede pensar en la solución a la NFA. Aun no sé si el mismo idioma puede ser la solución con la NFA.

El idioma para el DFA es $L = \{ ww : |w|=200 \}$.

Me podrían ayudar con esta parte de la tarea, mejor no con la solución real, pero con el asesoramiento?

P. S.: es mi primera tarea en este tema.

Answer 1

$L$ también debería funcionar para NFAs. Supongamos que $M$ es un NFA con menos de $2^{200}$ Estados que acepta cada palabra de $L$. Cada $u\in\{0,1\}^{200}$ sea $s_u=\langle s_u(0),s_u(1),\dots,s_u(400)\rangle$ la secuencia de Estados de $M$ a lo largo de algún camino que $M$ acepta $uu$. Entonces allí debe ser $u,v\in\{0,1\}^{200}$ tal que $u\ne v$ y $s_u(200)=s_v(200)$. Pero entonces $M$ acepta $uv\notin L$. Así, un NFA que acepta precisamente $L$ debe tener al menos $2^{200}=\left(2^{10}\right)^{20}>10^{60}$ Estados.