**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*_{0}, *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*_{0} (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 Σ.^{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 ...

Start Free Trial

No credit card required