Here is the explanation in Sipser's. For step 3, why should we accept only when none of the markers lie on an accept state? If the alphabet of the language is $\Sigma = \{a,b,c\}$, and after the first iteration, let's say $a$ and $b$ lie on the accept state while $c$ doesn't (meaning that c is not in the language). Thus, this language will not be in ALL-NFA because $M$ does not accept $c$. However, according to the procedure described below, the language will be rejected, because at this point there are 2 markers lying on an accept state:

Consider the language $ALL_{NFA} = \{\langle A \rangle: \text{$A$ is an NFA and $L(A) = \Sigma^*$}\}$.

The following nondeterministic linear space algorithm decides $ALL_{NFA}$.

Nondeterministically guess an input string rejected by the NFA and use linear space to guess which states the NFA could be at a given time. On input $\langle M\rangle$ where $M$ is an NFA:

  1. Place a marker on the start state of the NFA $M$.
  2. Repeat $2^q$ times, where $q$ is the number of states of $M$. 2.1 Nondeterministically select an input symbol and change the position of the markers on $M$’s states, to simulate reading that symbol.
  3. Accept if stages 2 reveals some string that $M$ rejects, i.e., if at some point none of the markers lie on accept states of $M$. Otherwise, reject.

1 Answer 1


Note that the procedure decides the complement of $ALL_{NFA}$, which is sufficient as $PSPACE = NPSPACE$.

The procedure checks whether the NFA $M$ rejects some input. The idea is simple, we actually simulate the run of the DFA $D$ that is obtained by applying the subset-construction on $M$ (a construction that keeps track of the set of states that $M$ can be in at any point in time, that is, the state-space of $D$ is $2^Q$, where $Q$ is the state-space of $M$). Clearly $|D|\leq 2^{|Q|}$. Hence, if $D$ rejects a word, then it rejects a word of length at most $2^{|Q|}$ as we can omit cycles from long rejecting runs of $D$.

Since we want to check whether $D$ rejects some word $w$ of length at most $2^{|Q|}$ using only linear space, we can guess the word $w$, letter after letter, while keeping track (1) only of the current letter of $w$, (2) only of the subset of states that $D$ reaches after reading the prefix of the $w$ that we've guessed so far (meaning, we do not write the whole description of $D$, but only the current subset of states that $D$ is in after reading the guessed prefix of $w$), and finally (3) we hold some counter to keep track at which iteration we're in (we can encode the iteration number in binary, which takes at most polynomial space in $|Q|$).

So the markers in a sense remember the subset of states that we described in item (2) above. If we marked at some iteration only rejecting states, it means that we've succeeded to guess so far a word that is rejected by $D$ (and thus rejected by $M$).

In your example, if the alphabet is $\Sigma = \{a, b, c\}$ where $c\notin L(M)$, then it suffices to guess on letter which is $c$ to see that all the states that are reachable from the initial state of $M$ upon reading $c$ are rejecting, and then we accept. So we mark only states that correspond to the current guessed letter, and not those that correspond to all possible guesses.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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