7
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Rick Decker Sep 3 '12 at 20:33
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Sep 3 '12 at 20:51
6
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – aplavin Sep 4 '12 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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