Solving Space Complexity of Sipser's NFA Algorithm

[gnome]

From Sipser's "Introduction to the Theory of Computation", pp. 278-279

Consider the problem of testing whether a nondeterministic finite automaton accepts any strings. Let
[tex] .\qquad ALL_{NFA} = \{<A>|\;A\text{ is a NFA and}\; L(A)} = \Sigma^*\}[/tex]
We give a nondeterministic linear space algorithm that decides the complement of this language, [itex]\overline{ALL_{NFA}}[/itex]. The idea behind this algorithm is to use nondeterminism to guess a string that is rejected by the NFA and to use linear space to keep track of which states the NFA could be in at a particular time. Note that this language is not known to be in NP or in coNP.

N = "On input <M> where M is an NFA:
1. Place a marker on the start state of the NFA
2. Repeat [itex]2^q[/itex] times, where q is the number of states of M:
3. ...Nondeterministically select an input symbol and change the positions
...of the markers on M's states to simulate reading that symbol.
4. If a marker was ever placed on an accept state, reject; otherwise accept."

If M accepts any strings it must accept one of length at most [itex]2^q[/itex] because in any longer string that is accepted the locations of the markers described in the preceding algorithm would repeat. The section of the string between the repetitions can be removed to obtain a shorter accepted string. Hence, N decides [itex]ALL_{NFA}[/itex].
The only space needed by this algorithm is for storing the location of the markers, and doing so only requires linear space. Hence the algorithm runs in nondeterministic space O(n).

I don't see why the maximum length of an accepted string is [itex]2^q[/itex]. I believe that [itex]2^q[/itex] is the number of possible combinations of marked states, since there are |q| states and each one can either be marked or unmarked. But why is that the limit of the length of an accepted string? In some particular NFA being simulated, there can be many [itex]Q \times \Sigma[/itex] pairs leading to a single state [itex]q_1[/itex], correct? So, doesn't it follow that it might require an input string much longer than [itex]2^q[/itex] before all of the [itex]2^q[/itex] combinations of state-markings are exhausted?

Am I misunderstanding something here?

 

[Jhero]

Yes, you are misunderstanding something. The reason that the maximum length of an accepted string is 2^q is because the algorithm only needs to run a maximum of 2^q times in order to check all possible combinations of marked states. After that it will have either accepted or rejected, so any longer strings will not be considered. This means that for any given NFA, the algorithm will run in O(2^q) time.

 

[tacman]

Your understanding is correct. The maximum length of an accepted string is not necessarily 2^q. The algorithm simply states that if an NFA accepts any strings, it must accept at least one string of length at most 2^q. This is because if a longer string is accepted, there will be a repetition of state-markings, which can be removed to obtain a shorter accepted string. This does not mean that all accepted strings will be of length 2^q, just that there exists at least one accepted string of length at most 2^q.

In some cases, it may require an input string much longer than 2^q before all combinations of state-markings are exhausted. However, the algorithm only needs to check for one accepted string, so it does not necessarily need to exhaust all combinations of state-markings.

Overall, the algorithm uses nondeterminism to guess a string that is rejected by the NFA, and then uses linear space to keep track of the states that the NFA could be in while simulating the string. This approach allows for a space complexity of O(n), making it a efficient solution for solving the space complexity of Sipser's NFA algorithm.