From Sipser's "Introduction to the Theory of Computation", pp. 278-279(adsbygoogle = window.adsbygoogle || []).push({});

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? 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; otherwiseaccept."

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,Ndecides [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).

Am I misunderstanding something here?

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Space Complexity

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

Loading...

Similar Threads - Space Complexity | Date |
---|---|

I Need to know the Topology on the Space of all Theories? | Oct 10, 2017 |

I Definition of "equivalent" probability problems? | Jun 25, 2017 |

A State Space and Probability Theory | Jun 15, 2017 |

B Calculus of Cantor Spaces (and the like)? | Mar 1, 2016 |

More space complexity: Savitch's Theorem | Jan 31, 2005 |

**Physics Forums - The Fusion of Science and Community**