δ : Q × ∪
×
(
{ })
Σ
Γ
λ
→ finite sub sets of Q × Γ
* is the
tran si tion func tion
q 0 = Ini tial state of the con trol unit ∈Q
Z = Stack start sym bol
F Q
⊆ = Set of Final states.
The arguments of δ are the current state of the control unit, the current
input symbol, and the current symbol on the top of the stack.
The result is a set of pairs (q, x)
where
q = next state of the con trol unit
x = string that is put on top of the stack in place of the sin gle
sym bol there before.
The ‘stack’ is an additional component available as part of PDA. The
‘stack’ increases its memory. With respect to {
|
},
a b n
n n
≥1 we can store a’s in
the stack. When the symbol ‘b’ is encountered, an ‘a’ from the stack can be
removed. If the stack becomes empty on the completion of processing a given
string, then the PDA accepts the string.
3.1.2 Tran si tion Func tions for NPDA
The transition function for an NPDA has the form
δ
λ
:
(
{ })
Q × ∪
× →
Σ
Γ Finite sub sets of Q × Γ
δ is now a function of three arguments.
The first two arguments are the same as before:
(i) the state
(ii) either λ, or a symbol from the input alphabet.
The third argument is the symbol on top of the stack. Just as the input
symbol is “consumed” when the function is applied, the stack symbol is also
“consumed” (removed from the stack).
160
Theory of Automata, Formal Languages and Computation
a
Input File
Finite State
Control
Z
Pushdown Store
Fig. Model of Pushdown Autom a ton (PDA)