4.2  PDA COMPUTATIONS 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 = ImagesΣ, Γ, Q, δ, q0, FImages

where the finite set Σ is the input alphabet; Q is a finite set of states; δ is the “program”, that is, the transition relation; q0 (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 Σ ∩ Γ ≠ Images.

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 Σ.126 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 ...

Get Theory of Computation now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.