Problem Detail: In Sipser’s book there is a section describing how to decide $qquaddisplaystyle mathrm{ALL}_mathrm{NFA} = { langle N rangle mid N text{ is an NFA}, L(N) = Sigma^*}$ in polynomial space. To do so, it shows $overline{mathrm{ALL}_mathrm{NFA} }$ is in NPSPACE. I don’t understand this part: If $M$, the NTM deciding the language, rejects any strings, it must reject one of length at most $ 2^q $ where $q$ is the number of states in $M$. For any longer string that is rejected, some states would repeat. But why? Is there any alternative explanation that helps in understanding this part?
Asked By : CentAu
Answered By : Louis
Your question is really about the following statement: If an NFA with $n$ states does not accept every string, then it rejects some string of length at most $2^n$. (The rest of the proof comes from the fact that REACH is in NL.) To see why this is so, first let’s look at a DFA with $k$ states that does not accept every string. The transition function of the DFA corresponds to a directed graph $G$ on $k$ vertices. DFA computations bijectively correspond to walks in $G$ starting from the vertex $s$ representing the start state. Since the DFA does not accept every string, there is a vertex representing a non-accepting state $j$ reachable by a walk from $s$. In particular, there is a simple path $P$ from $s$ to $j$, which can have length at most $k$ (e.g., DFS will produce one). $P$ corresponds to a string of length at most $k$ that is not accepted. The NFA question reduces to the DFA one. Using the powerset construction, convert the NFA with $n$ states to a DFA with $k = 2^n$ states and then use the above argument.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/24390 3.2K people like this
