# Space Complexity

1. Jan 30, 2005

### gnome

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 $2^q$. I believe that $2^q$ 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 $Q \times \Sigma$ pairs leading to a single state $q_1$, correct? So, doesn't it follow that it might require an input string much longer than $2^q$ before all of the $2^q$ combinations of state-markings are exhausted?

Am I misunderstanding something here?