Does an NFA with a non-empty anf non-full language recognize a string with of length at most its number of states?

Question

Let $N = (Q,\Sigma,\Delta,s,F)$ be an NFA (nondeterministic finite automaton) such that $L(N)\ne \emptyset$ and $L(N)\ne \Sigma^*$. Prove or disprove the following.

$$\exists x \in L(N): \lvert x \rvert \le \lvert Q \rvert.$$

Answer 1

SKETCH: Pick a word $w\in L(N)$. It must be able to drive $N$ from $s$ to a state in $F$. Look at such a computation. If it repeats a state, it has a loop; remove the segment of $w$ that produced the loop to get a shorter word that drives $N$ to the same state in $F$. By starting with a word of minimal length that drives $N$ to that state, you can assume that the computation does not repeat a state. There must be at least as many transitions in the computation as there are letters in $w$, so ...