I'm trying to prove that this is true but cannot find a good way to show this proof. The question is below:
Let $T$ be an NFA such that the language defined by $T$ is neither empty nor $\Sigma^*$. Show that there must be a string $b$ in the language defined by $T$ such that the length of $b$ is less than or equal to the the number of states in $T$.
Does anyone have a good way to prove this?
Best Answer
Let $w$ be the shortest string accepted by your NFA, and suppose it has length greater than the number of states. This means that while reading $w$, your NFA was twice in the same state. Suppose $w=w_1...w_k...w_l...w_n$ and that when reading $w_k,w_l$ NFA is in the same state. Here are two claims which I leave up to you to prove:
If $k=1$ (i.e. $w=w_k...w_l...w_n$), then $w_l...w_n$ is a shorter string accepted by the NFA.
If $k>1$, then $w_1...w_{k-1}w_l...w_n$ is a shorter string accepted by the NFA.
On both cases we have a clear contradiction.