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
0
loop transition, push0
on stack, state staysq2
- Take
1
transition, 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
01
on the input string with no exits out ofq4
, so accept... or assume dead state somehow?