In Sipser's Theory of Comp in 2.2 the following PDA is provided for ${\{0^n1^n|n\ge0}\}$.

enter image description here

I follow how to process "", "01", "0011". I want to reject "0101", however it seems one of the nondeterministic paths makes it to accept. I'm probably misunderstanding a detail of PDA -- my logic is as follows:

  1. Start in q1
  2. Take $\varepsilon$ transition, push $ on stack, state is now q2
  3. Take 0 loop transition, push 0 on stack, state stays q2
  4. Take 1 transition, pop the 0, update state to q3
  5. Take $\varepsilon$ transition, pop $ off, enter accept state q4
  6. The other path is ignored out of q3
  7. But we've still got another 01 on the input string with no exits out of q4, so accept... or assume dead state somehow?

1 Answer 1


Being in state $q_4$ and still having $01$ to read means that the word cannot be accepted (at least with this reading path).

Using this formal definition, there is no path leading from the configuration $(q_0, 0101, Z)$ to a configuration $(q, \varepsilon, \gamma)$, so $0101$ is not accepted by the automaton.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.