Existence of NFA for this language

Question

I'm given a task to find (and prove) such language $L$ in the alphabet $\Sigma = \{a,b\}$ with all words less than $1000$ in length, for which any DFA/NFA will have more than $10^{10}$ of states. For the first part of the task, with DFA, I've found such language (see below), but can't think of solution for NFA. I even don't know if the same language can be the solution with NFA.

The language for DFA is $L = \{ ww : |w|=200 \}$.

Could you help me with this part of task, better not with actual solution, but with advice?

P.S.: it's my the very first homework on this topic.

Answer 1

$L$ should also work for NFAs. Suppose that $M$ is an NFA with fewer than $2^{200}$ states that accepts every word of $L$. For each $u\in\{0,1\}^{200}$ let $s_u=\langle s_u(0),s_u(1),\dots,s_u(400)\rangle$ be the sequence of states of $M$ along some path by which $M$ accepts $uu$. Then there must be $u,v\in\{0,1\}^{200}$ such that $u\ne v$ and $s_u(200)=s_v(200)$. But then $M$ accepts $uv\notin L$. Thus, an NFA that accepts precisely $L$ must have at least $2^{200}=\left(2^{10}\right)^{20}>10^{60}$ states.