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 = 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:

Images

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 O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.