Definition 5.1.1: a pushdown acceptor (PDA) M is a 7-tuple, M = (S, _______, s0, Z, R), where S (states), _ (input alphabet), and _ (stack symbols) are finite non-empty sets, s0_S (initial state), Z__ (start symbol), R _ S (recognition states, or final states), and _: S _ (_ _ {_}) _______finite subsets of S ___* (transition function).
Definition 5.1.2: given a PDA M = (S, _______, s0, Z, R), an instantaneous description (ID) is a triple
Note that PDAs are non-deterministic and admit _-moves on input (but not stack) from the outset.
| Previous slide | Next slide | Back to first slide | View graphic version |