This problem appears in Michael Sipser's book Theory of Computation. My question isn't about the statement itself, which is rather obvious, but rather why the bound can't it be improved to a string of length at most k-1? In other words, is there an example where a non empty regular language is recognized by an NFA with k states whose least string has length k?
If a non-empty regular language has k-state NFA recognizing it, it has a string of length at most k
automatacomputer scienceregular-language
Best Answer
No:
Consider a $k$-state NFA with a final state $F$ reachable from an initial state $I$.
Then the shortest path from $I$ to $F$ sees at most $k$ states, as otherwise there would necessarily be a cycle, and thus a shorter path.
But the word accepted by this path corresponds to the number of edges in the path, which is 1 less than the number of states.
Then the length of the shortest word is $$l = \text{number of edges} = \text{number of nodes} - 1 \leq k - 1$$
Hope this helps! ^_^