Let $M$ be an NFA with alphabet {0,1} that accepts every binary string. Which of the following is true?
a) Every state of $M$ must be an accept state
b) $M$ does not have any accept state
c) The start state of $M$ must be an accept state
d) None of the above
I think the answer is c, but that is only from process of elimination as I don't believe a or b can be true since a NFA by definition has accepting state, and I believe a binary string needs to have at least length 2. I am not sure why the answer is C though, can anyone explain this to me? Thank you in advance!
If you don't have a definition for binary string then I would interpret it as {0,1}*, that is the set of all finite words made of 0 and 1, including words of lenght 1 and the empty word.
For a) you could find a counter example, i.e. a NFA that accepts all those words and still has non-accpeting states.
b) cannot be true, since a NFA without accepting states wouldn't accept any word.
c) is true, if your NFA is not allowed to have transitions with the empty words. If the start state would not be an accept state, the NFA wouldn't accept the empty word and therefore not every binary string. (This depends on the definition of a binary string again.)