2
$\begingroup$

I'm trying to understand Sipser's example showing that $ALL_{nfa} \in Co-NSPACE(n)$, where $$ALL_{nfa} = \{ <A> | A \text{ is an NFA such that } L(A) = \Sigma^*\}.$$

The algorithm can be seen here.

I'm confused by a few things, but mainly what is meant by "nondeterministically select an input symbol"? If I "nondeterministically" choose symbol 'a' and then mark all the vertices I can reach from the current ones by 'a', then don't I possibly miss out on the vertices reachable by 'b'? And even though we repeat this $2^q$ times, what's to stop me from choosing that 'a' transition each time?

If my instincts are correct, then what we are trying to do is convert the nfa to a dfa (which will have at most $2^q$ states). If the dfa has a single reject state, then we know the nfa has a string that will be rejected. However, we would like to do this without actually converting to a dfa, which might require too much space. So the provided algorithm tries to traverse the corresponding dfa graph, without actually building it?

Improve this question
$\endgroup$
5
$\begingroup$

To show that $ALL_{\mathsf{NFA}}$ is in $\mathrm{co-NSPACE}(n)$, we must show that the complement $\overline{ALL_{\mathsf{NFA}}}$ is in $\mathrm{NSPACE}(n)$.

The complement is

$$\overline{ALL_{\mathsf{NFA}}} = \{ \langle N \rangle \mid N \text{ is an NFA where } L(N) \neq \Sigma^* \}$$

To show that $\overline{ALL_{\mathsf{NFA}}}$ is in $\mathrm{NSPACE}(n)$ we therefore need to devise a Turing machine that, given an NFA description $\langle N \rangle$ can tell us if there exists an input that $N$ will not accept.

Essentially, the machine will nondeterministically guess a string $w$ and verify that this string is not accepted by $N$. Our machine may guess the wrong string, but remember that the machine is nondeterministic -- as long as it is possible to guess a string with this property, the machine will accept $\langle N \rangle$.

To guess such a string $w$ and check that the NFA does not accept it, we need to explore all the possible computations of $N$ on $w$ and show that none of them will lead to an accepting state. This does not require us to construct an equivalent DFA using the subset construction; doing this would require more than linear space. However, even just storing all of the computations of $N$ on $w$ on the Turing machine tape will require more than $n$ tape cells.

The trick is to guess the string symbol by symbol and keep track of the sets of states that $N$ could possibly be in after it has read a symbol. If $N$ has $q$ states, there are $2^q$ such sets of possible states. We start with the set $\{ q_0 \}$ and guess a sequence of $2^q$ symbols. For each symbol that we guess, we record the subset of states that can be visited from any of the states that $N$ could be in now. We can keep track of this subset of possible current states using $q$ bits (represented as $q$ cells on the tape). This is linear in $n$ where $n$ is the length of $\langle N \rangle$. This description must at the very least list the states of $N$, so $q = O(n)$.

If the set of possible current states that we are now in does not contain an accept state, then we have found a string that cannot be accepted by $N$. We may have to guess $2^q$ symbols, since each symbol could in principle lead us to a new set of possible current states that had not been seen before. But once all sets of possible current states have been examined, we can stop. We can count to $2^q$ in binary using no more than $q$ bits. Again this requires no more than $O(n)$ bits.

Improve this answer
$\endgroup$
12
  • $\begingroup$ Nice explanation! Perhaps it's also worth briefly mentioning why the NFA state transitions cannot be guessed and have to be all simulated, as this is a usual point of confusion with this proof. $\endgroup$ – aelguindy Nov 1 '16 at 22:32
  • $\begingroup$ See the part of my answer that begins with "To guess such a string..." $\endgroup$ – Hans Hüttel Nov 1 '16 at 22:39
  • $\begingroup$ Yes I am not saying you did not mention that all paths need to be checked. I am saying that a confused reader might wonder why not use non-determinism to check a single path. Not pointing errors in your answer, just suggesting an improvement :). $\endgroup$ – aelguindy Nov 1 '16 at 22:46
  • $\begingroup$ I'm still missing a main point somewhere... I understand that we can check all the possible computations of $N$ on $w$ by doing a sort of breadth first search using $w$ as our guide. What I'm still blocking on is the "nondeterministic guess" of $w$. If we guess the string "aaabbb....." and check all possible computations on it, couldn't we miss out on the results of trying something like "bbbaaa....? $\endgroup$ – theQman Nov 1 '16 at 22:53
  • $\begingroup$ @theQman. To make life simple, let's say the alphabet is $\{a,b\}$. Then our machine will guess that the first symbol of $w$ is $a$ and (in another universe, if you like) will also guess that the first symbol is $b$. Continue this "cloning of universes" for the second symbol, the third, and so on. That's how nondeterminism works: if there's any universe in which $N$ doesn't accept its particular version of the input, we've found what we needed. $\endgroup$ – Rick Decker Nov 1 '16 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.