Question regarding Theory of Computation homework... please help!

[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!!!

[bascule]

If I understand correctly, you're asking why the reverse of a regular language must be able to match a string whose length is at least two to the power of the number of states of an NFA which describes the original language.

 

If that's true, I'll have to do some research into the reverses of regular languages...