In Sipser's Theory of Comp in 2.2 the following PDA is provided for ${\{0^n1^n|n\ge0}\}$.
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:
- Start in
q1 - Take $\varepsilon$ transition, push
$on stack, state is nowq2 - Take
0loop transition, push0on stack, state staysq2 - Take
1transition, pop the0, update state toq3 - Take $\varepsilon$ transition, pop
$off, enter accept stateq4 - The other path is ignored out of
q3 - But we've still got another
01on the input string with no exits out ofq4, so accept... or assume dead state somehow?
