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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted



Similar Discussions: Space Complexity
  1. Sample space (Replies: 1)

  2. Probability spaces (Replies: 2)

  3. Sample Space (Replies: 9)

Loading...