Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Space Complexity

  1. Jan 30, 2005 #1
    From Sipser's "Introduction to the Theory of Computation", pp. 278-279
    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?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted