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.

  • 0
    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.)2012-09-03
  • 1
    @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.2012-09-03

1 Answers 1

6

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

  • 0
    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.2012-09-04