Theory of Computation

4.2  PDA COMPUTATIONS

4.2.0.5 Definition. (PDA) A pushdown automaton or PDA, M, is a NFA equipped with a stack variable whose contents we will generically denote by lowercase Greek letters from the beginning of the alphabet (α, β, γ) with or without primes.

Algebraically speaking, M is a toolbox

M = Σ, Γ, Q, δ, q₀, F

where the finite set Σ is the input alphabet; Q is a finite set of states; δ is the “program”, that is, the transition relation; q₀ (generic name!) is a distinguished member of Q, the start state; F is a finite set of accepting states.

Γ is new: It is a finite alphabet of stack symbols. The stack variable takes values from Γ^*. It is allowed to have Σ ∩ Γ ≠ .

The set of instructions (program) is encoded into the relation δ. A PDA has only four types of possible instructions, given below in flow-diagram form:

where, generically, an “A” denotes a member of Γ and an “a” denotes a member of the input alphabet Σ.¹²⁶ The first and third are “mixed” instructions (both input and stack activity), while the second and fourth are “pure” (stack activity only). The second is a “pure push ...