lemontree

Howdy folks, This is a question regarding a problem that was assigned to my class about a week ago. No one in the class could solve it, and then when we asked the teachers, they couldn't either. Additionally, one of our teachers actually wrote a proof disproving the statements made in the problem. Let me preface the problem by saying that I have tried, extensively, to solve it - to the point of feeling like a complete dumbass for not being able to get it. I have asked quite a few other people, and no one has been able to come up with anything helpful. Let N be an NFA with k states that recognizes some language A. a) Show that, if A is nonempty, A contains some string of length at most k. b) Show that, by giving an example, part (a) is not necessarily true if you replace both A's by ~A. c) Show that, if ~A is nonempty, ~A contains some string of length at most 2^k. The class was able to solve part (a); it was part (b) that gave us trouble, and part © (where it defines the limit of a string in ~A) only complicated matters. My teacher's proof disproving the problem goes like this: Goal: To show that if A contains all strings of k or less length, ~A is empty. There are two ways in which a string in ~A would fail: it would end in a non-accept state, or it would reach a state where there is no arrow for an input received. For the first of these, given that the string is in ~A, it must have length at least k+1. Because it's length k+1, it must repeat a state somewhere in its path - as such, it would be possible to remove the characters that occur in the string between the first instance of the state and the latter, thereby resulting in a string < k+1; this contradicts our choice of s. (as well as the definition of what language A is) For the second possibility, let's imagine that q is the state the machine is in before it receives an input for which there are no arrows. The state q must be reachable in at most k-1 steps (it can be reached, because our string reaches it, and as there are k states removing any sections between repeated states in the processing of s leaves a path with at most k-1 arrows). Make a new word t of length at most k that gets to q in at most k-1 steps and then has the symbol that forced M to reject s. The word t is rejected, again contradicting our choice of s. Presumably there's an error somewhere... either in my teacher's proof, or the question in the book. I THINK that my teacher's proof is correct, but that it isn't considering one of the options the question is considering (as the question clearly states "if ~A is nonempty"). Unfortunately, I don't know how the original problem needs to be approached to get by this . Any help would be GREATLY appreciated!!!