The question asks the following: "Let N be a nondeterministic finite automaton with s states. Suppose than N accepts all strings of length s or
less. Does it follow that N accepts all strings? (If so, give a proof. If not, give a counter-example.)"
An idea that I've been getting is that since this would be an NFA, it can just be constructed with a certain number of states and thus have the ability to have one state transition to another, and say there are 5 states, there would be 4 transitions, where the 5th state would be the accepting state. Putting it in general terms, there could be k states, and k-1 transitions between all the states where one state moves to the next. This would accept a string with length less than the number of states. Would this be a correct approach or is there another way that would work more effectively? Thanks!
Best Answer
An NFA with $5$ states and an input alphabet of $m$ symbols could have as many as $5(m+1)$ transitions, if you allow $\epsilon$-transition, or $5m$ transitions, if you do not allow them. But more to the point, what you’ve written so far doesn’t really even approach the question. First you have to decide whether the answer to the first question is yes or no; then you have to justify your answer, with a proof for yes or an example for no.
HINT: The answer is no, but I don’t know a really small example: the smallest that I know has $11$ states and accepts every input of length at most $29$. Instead of describing it, I’ll tell you where to find it and let you try to dig it out: the NFA is the machine $N_3$ described in the proof of Lemma $2$ of this PDF. You can ignore the proof itself: just try to draw $N_3$ from the description int the first paragraph of the proof and verify that it has $11$ states, accepts $1^n$ for $n<30$, and rejects $1^{30}$.