O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required