Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Just to be pedantic, any DFA is by definition an NFA, so you've already answered the second question. That's probably not what the problem is looking for, though. (Insert emoticon here.) – Rick Decker Sep 3 '12 at 20:33
@Rick: The implication goes the other way. Had chersanya shown that any NFA for $L$ requires more than $10^{10}$, the question would automatically have been completely answered, for the reason that you give. – Brian M. Scott Sep 3 '12 at 20:51
up vote 6 down vote accepted

$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.

share|cite|improve this answer
+1 for this simple modification for NFAs. Nice job. – Rick Decker Sep 4 '12 at 0:28
Thanks, I have almost the same proof for DFA, but didn't think of looking on one of acceptance paths instead of determined sequence of states. – aplavin Sep 4 '12 at 7:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.