Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 295

abb...

M

Z 0

:

:

H

p Finite Control

...

x

g

A

Fig. 11.20(b)

Language of a PDA

Finally, we define the language of a PDA. There are two natural ways to define the language

accepted by a PDA. The first will be the acceptance by the empty stack mechanism and second

will be the acceptance by the final state mechanism.

Acceptance by Empty Stack Mechanism

As we have seen that language accepted by the PDA is the set of all input alphabets for which

some sequence of moves causes the PDA to empty the stack no matter in what state PDA is in

that instant. Assume M be a PDA and its language be N(M) then

N (M) = {x ∈ Σ* / (q 0 , x, Z 0 )

M

* (q, ∈, ∈)}

Acceptance by Final State Mechanism

In this way we define the language accepted by the PDA similar to the way a FA accepts the
inputs. Such that we designate some states as final states and define the language as the set of
all input alphabets for which some choice of moves causes the PDA to reach to the final state
no matter what stack pointer points to. Assume M be a PDA and its language be L(M) then
L (M) = {x ∈ Σ* / (q 0 , x, Z 0 )
M

* (p, ∈, γ)}

Note for a particular PDA M both definitions of acceptance i.e., N(M) and L(M) are not always equiva-
lent but of course they are both context free languages (CFLs).
Although the acceptance by final state mechanism is the more common notation, but
the acceptance by the empty stack mechanism provides an easier way to prove the basic theo-
rems of PDA. In the latter examples we will construct the PDA by assuming that the given
language is the language accepted by empty stack.
Example 11.15. Construct a PDA for the language L = {ai bi / i ≥ 1}.
Sol. Since language L is a context free language whose grammar will be S → ab / aSb so an
equivalent PDA can be constructed. Also assume L = N(M), where PDA M will be
M = ({q 1 , q 2 }, {a, b}, {Z 0 , X), δ, q 1 , Z 0 , Ø)
The moves are as follows,
•δ (q 1 , a, Z 0 ) → {(q 1 , XZ 0 )} [Corresponding to the first input alphabet a, stack sym-
bol X will be pushed]
•δ (q 1 , a, X) → {(q 1 , XX)} [For the consecutive occurrences of a’s, same stack sym-
bol X will be pushed again]