Lecture 10 (Computation Theory) Pushdown Automata, Non-Context-Free Languages, and Pumping Lemma 2.0

A PDA's transition function differs from an NFA's in that, in addition to a state and an input symbol, it also takes:

1. A.A counter value tracking how many input symbols have been read
2. B.A symbol popped off the top of the stack (possibly the empty string)
3. C.The full remaining contents of the input tape as a string
4. D.A second state used to break non-deterministic ties