CSO-322 Theory of Computation

Unit-4: Pushdown Automata

Dr. Lavanya Selvaganesh

Dr. Lavanya Selvaganesh CSO322 1 / 32

PDA - Introduction
Let G be a CFG having productions S → aSa|bSb|c.
G generates the language L = {xcx R |x ∈ (a, b)∗ } i.e. L contains
strings which are odd length palindrome over {a, b} with the
middle symbol c. ’c’ can be thought as a marker in the middle
easy to recognize the string.
For recognizing strings in L using a single left to right pass, we
design an algorithm:
Save the symbols in the first half of the string as we read
them, so that once we encounter the c, we begin matching
incoming symbols with symbols already read.
To do this, we retrieve the saved symbols using the rule
LAST-IN-FIRST-OUT (LIFO).
The data structure incorporating the LIFO rule is a stack and is
usually implemented as a list in which one end is designated as
top.

Dr. Lavanya Selvaganesh CSO322 2 / 32

PDA - Introduction
The set of states Q = {q0 , q1 , q2 }.
q0 (initial state) is sufficient for processing the first half of the
string.
In this state, each input symbol is pushed onto the stack,
regardless of what is currently on top.
The machine stays in q0 as long as it has not yet received the
symbol c; when c is received as an input the machine moves to
state q1 , leaving the stack unchanged.
State q1 is for processing the second half of the string.
Once the machine enters this state, the only string can be
accepted is the one whose second half is the reverse of the string
already read.
In this state, each symbol is compared to the symbol currently on
top of the stack.
If the symbols are matched, that symbol is popped off the stack
and both are discarded.
Dr. Lavanya Selvaganesh CSO322 3 / 32
PDA - Introduction
Otherwise, the machine will crash and the string will not be
accepted.
This phase of the processing ends when the stack is empty and
the machine has not crashed.
An empty stack means that every symbol in the first half of the
string has been successfully matched with an identical input
symbol in the second half and at that point machine enters the
accepting state q2 .
Each move of the machine will be determined by three things:
▶ The current state
▶ The next input
▶ The symbol on the top of the stack
and will consists of two parts:
▶ Changing states(or the next state)
▶ Replacing the top stack symbol by a string of zero or more symbols.

Dr. Lavanya Selvaganesh CSO322 4 / 32

PDA - Formal Definition
Formal Definition
A PDA is a 7-tuple M = (Q, Σ, Γ, q0 , z0 , A, δ) where -
Q: finite set of states
Σ and Γ: finite sets (Input and stack alphabets respectively)
q0 : initial state, q0 ∈ Q
z0 : initial stack symbol, z0 ∈ Γ
A: set of accepting states in a subset of Q
δ : Q × (Σ ∪ {ϵ}) × Γ → P(Q × Γ∗ ) called transition function of M,
where P denotes the power set.

A configuration of the PDA M = (Q, Σ, Γ, q0 , z0 , A, δ) is a triple

(q, x, α) where q ∈ Q, x ∈ Σ∗ , α ∈ Γ∗ .
Current configuration of M denoted by (q, x, α) means q is the
current state, x is the string of remaining unread input and α is the
current stack contents, where left end of α corresponds to the top
of stack.
Dr. Lavanya Selvaganesh CSO322 5 / 32
PDA - Formal Definition

Let (p, x, α) ⊢M (q, y , β) mean that the first configuration takes M

to the second configuration.
Here x = ay , a ∈ Σ ∪ {ϵ}
The string β of stack symbols is obtained from α by replacing the
first symbol X by a string ξ. (In other words, α = X Υ, for some
X ∈ Γ and some Υ ∈ Γ∗ , and β = ξΥ for some ξ ∈ Γ∗ ) and
(q, ξ) ∈ δ(p, a, X ).
In general, we write (p, x, α) ⊢∗M (q, y , β), if there is a sequence of
zero or more moves that takes M from the first configuration to the
second.

Dr. Lavanya Selvaganesh CSO322 6 / 32

Acceptance by a PDA

PDA accepts a string in two manners:

1 Acceptance by final state
2 Acceptance by empty stack
If M = (Q, Σ, Γ, q0 , z0 , A, δ) is a PDA and x ∈ Σ∗ , x is accepted by
M, if (q0 , x, z0 ) ⊢∗M (q, ϵ, α) for some α ∈ Γ∗ and some q ∈ A.
A language L ⊆ Σ∗ is said to be accepted by M if L is precisely the
set of strings accepted by M; in this case, L = L(M).
This type of acceptance is called acceptance by final state.

Dr. Lavanya Selvaganesh CSO322 7 / 32

PDA - Example (Palindrome)

M = (Q, Σ, Γ, q0 , z0 , A, δ) for L = {wcw R : w ∈ {a, b}∗ }

where Q = {q0 , q1 , q2 }, Σ = {a, b, c} = Γ, z0 = ϵ, A = {q2 },
δ is given by

Dr. Lavanya Selvaganesh CSO322 8 / 32

PDA - Example (Simple Palindrome)
Transition Table

String w = abcba: accepted and w = acaa: rejected.

Dr. Lavanya Selvaganesh CSO322 9 / 32

Acceptance by a PDA- Notable points

When a string x is accepted by a PDA, the stack may or may not

be empty.
When we say a string x is accepted by a PDA, we mean that there
is a sequence of moves that cause the machine to reach an
accepting configuration as a result of reading the symbols of x.
Since a PDA can be non-deterministic there may be many other
possibilities of sequences of moves that do not lead to an
accepting configuration. Each time there is a choice of moves, we
view the PDA as making a guess as to which one to choose.
Acceptance means that if the PDA guesses right at each step, it
can reach an accepting configuration.

Dr. Lavanya Selvaganesh CSO322 10 / 32

PDA - Example (Palindrome)
L = {w = w R : w ∈ {a, b}∗ }
Note: Here the machine must "guess" when it has reached the middle
of the input string and change from state q0 to state q1 in a
non-deterministic fashion.
Let M = (Q, Σ, Γ, q0 , z0 , A, δ) where δ is given by the transition table:

Dr. Lavanya Selvaganesh CSO322 11 / 32

PDA - Example (Palindrome)
Computation tree for the PDA with input baab

Dr. Lavanya Selvaganesh CSO322 12 / 32

The sequence of moves that leads to the acceptance is:

(q0 , baab, z0 ) ⊢ (q0 , aab, bz0 )

⊢ (q0 , ab, abz0 )
⊢ (q1 , ab, abz0 )
⊢ (q1 , b, bz0 )
⊢ (q1 , ϵ, z0 )
⊢ (q2 , ϵ, z0 ), [Accept]

Dr. Lavanya Selvaganesh CSO322 13 / 32

Deterministic Pushdown Automaton

Let M = (Q, Σ, Γ, q0 , z0 , A, δ) be a PDA.

M is deterministic if there is no configuration for which M has a
choice of more than one move. In other words, M is deterministic
if it satisfies both the following conditions:
1 For any q ∈ Q, a ∈ Σ ∪ (ϵ) and X ∈ Γ, the set δ(q, a, X ) has almost
one element.
2 For any q ∈ Q, and X ∈ Γ, if δ(q, ϵ, X ) ̸= ϕ then for every
a ∈ Σ, δ(q, a, X ) = ϕ.
A language L is a deterministic context-free language (DCFL) if
there is a deterministic PDA (DPDA) accepting L.

Dr. Lavanya Selvaganesh CSO322 14 / 32

DPDA - Example (Balanced Strings of Brackets)

Consider the language L of all balanced strings involving two

types of brackets: {} and [].
L is the language generated by CFG with productions:
S → SS|[S]|{S}|ϵ
The PDA will have two states: initial state q0 , which is also the
accepting state (ϵ ∈
/ L) and another state q1 .

Dr. Lavanya Selvaganesh CSO322 15 / 32

Transition Table:

Move No. State Input Stack Symbol Move

1 q0 { z0 q1 , {z0
2 q0 [ z0 q1 , [z0
3 q1 { { q1 , {{
4 q1 [ { q1 , [{
5 q1 { [ q1 , {[
6 q1 [ [ q1 , [[
7 q1 } { q1 , ϵ
8 q1 ] [ q1 , ϵ
9 q1 ϵ z0 q0 , z0

Check for input- {[]}[] (accepted)

Dr. Lavanya Selvaganesh CSO322 16 / 32

DPDA - Example (Equal number of a’s and b’s)
L = {x ∈ {a, b}∗ |na (x) = nb (x)}

The above transition table contains ϵ (Please read Λ as ϵ).

Check for string x=abbaaabb (accepted) and aabbbaa (rejected).
Exercise: L = {x ∈ {a, b}∗ |na (x) > nb (x)}

Dr. Lavanya Selvaganesh CSO322 17 / 32

Removing ϵ transitions
There are 3 ways to remove the ϵ transition in a PDA.
Count one a and start pushing when you encounter two a’s.
Or use another stack symbol for the first a.
Or introduce a new state for the case there is exactly one extra a.
The transition table after removing the ϵ-symbol.

Dr. Lavanya Selvaganesh CSO322 18 / 32

DPDA - Not always possible

Theorem
The language of palindrome {w ∈ {a, b}∗ |w = w R } cannot be
accepted by a DPDA.

Dr. Lavanya Selvaganesh CSO322 19 / 32

Acceptance by Empty Stack

For each PDA P = (Q, Σ, Γ, δ, q0 , z0 , F ), we also define

N(P) = {w|(q0 , w, z0 ) ⊢∗ (q, ϵ, ϵ)} for any state q.

Theorem
Suppose M = (Q, Σ, Γ, q0 , z0 , A, δ) is a PDA accepting the language
L ⊆ Σ∗ . Then there is another PDA M1 = (Q1 , Σ1 , Γ1 , q1 , z1 , A1 , δ1 )
accepting L by empty stack.
In other words, for any string x ∈ L if and only if (q1 , x, z1 ) ⊢∗M1 (q1 , ϵ, ϵ)
for some state q ∈ Q1 .

There are two ways:

1 From final state to empty stack
2 From empty stack to final state

Dr. Lavanya Selvaganesh CSO322 20 / 32

From Final State to Empty Stack

Theorem
Let L be L(PF ) for some PDA PF = (Q, Σ, Γ, δF , q0 , z0 , A). Then there
is a PDA PN s.t. L = N(PN ).

PN = (Q ∪ {p0 , p}, Σ, Γ ∪ {X0 }, δN , p0 , X0 ) where-

1 δN (p0 , ϵ, X0 ) = {(q0 , z0 X0 )}
2 For all states q ∈ Q, a ∈ Σ or a = ϵ, Y ∈ Γ,
δN (q, a, Y ) = δF (q, a, Y ) contains every pair in δF (q, a, Y ).
3 For all accepting states q ∈ A, Y ∈ Γ or Y = X0 , δN (q, ϵ, Y )
contains (p, ϵ).
4 For all stack symbols Y ∈ Γ, or Y = X0 , δN (p, ϵ, Y ) = {(p, ϵ)}.

Dr. Lavanya Selvaganesh CSO322 21 / 32

From Empty Stack to Final State

Theorem
If L = N(PN ) for some PDA PN = (Q, Σ, Γ, δN , q0 , z0 , A). Then there is
a PDA PF s.t. L = L(PF ).

PF = (Q ∪ {p0 , pf }, Σ, Γ ∪ {X0 }, δF , p0 , X0 , {pf }) where-

1 δF (p0 , ϵ, X0 ) = {(q0 , z0 X0 )}
2 For all states q ∈ Q, a ∈ Σ or a = ϵ, Y ∈ Γ, δF (q, a, Y ) contains all
pairs in δN (q, a, Y ).
3 In addition to (2), δF (q, ϵ, X0 ) contains (pf , ϵ) for every state q ∈ Q.

Dr. Lavanya Selvaganesh CSO322 22 / 32

PDA corresponding to given CFG

Definition: Top-Down PDA corresponding to a CFG

Let G = (V , Σ, S, P) be a context-free grammar. We define
M = (Q, Σ, Γ, q0 , z0 , A, δ) as:
Q = {q0 , q1 , q2 },
A = {q2 },
Γ = V ∪ Σ ∪ {z0 } where z0 ∈ / V ∪ Σ.

The initial move of M is to place S on the stack and move to q1 :

δ(q0 , ϵ, z0 ) = {(q1 , Sz0 )}.
The only move to the accepting state q2 is from q1 , when the stack
is empty except for z0 : δ(q1 , ϵ, z0 ) = {(q2 , z0 )}.
Otherwise the only moves of M are:
1 For every A ∈ V , δ(q1 , ϵ, A) = {(q1 , α)|A → α is a production in G } .
2 For every a ∈ Σ, δ(q1 , a, a) = {(q1 , ϵ)}.

Dr. Lavanya Selvaganesh CSO322 23 / 32

CFG to PDA: Example
Example
L = {x ∈ {a, b}∗ |na (x) > nb (x)}
CFG: S → a | aS | bSS | SSb | SbS.

Construct PDA M = (Q, Σ, Γ, q0 , z0 , A, δ) where Q = {q0 , q1 , q2 },

Σ = {a, b}, Γ = {S, a, b, z0 }, A = {q2 } and transition function:

State Input Stack Symbol Moves

q0 ϵ z0 (q1 , Sz0 )
q1 ϵ S {(q1 , a), (q1 , aS), (q1 , bSS) ,
(q1 , SSb), (q1 , SbS)}
q1 a a {(q1 , ϵ)}
q1 b b {(q1 , ϵ)}
q1 ϵ z0 (q2 , z0 )
All other Combinations No Moves

Dr. Lavanya Selvaganesh CSO322 24 / 32

CFG to PDA: Example
Let us consider- x = abbaaa ∈ L
(q0 , abbaaa, z0 ) ⊢ (q1 , abbaaa, Sz0 ) S
⊢ (q1 , abbaaa, SbSz0 ) ⇒ SbS
⊢ (q1 , abbaaa, abSz0 ) ⇒ abS
⊢ (q1 , bbaaa, bSz0 )
⊢ (q1 , baaa, Sz0 )
⊢ (q1 , baaa, bSSz0 ) ⇒ abbSS
⊢ (q1 , aaa, SSz0 )
⊢ (q1 , aaa, aSz0 ) ⇒ abbaS
⊢ (q1 , aa, Sz0 )
⊢ (q1 , aa, aSz0 ) ⇒ abbaaS
⊢ (q1 , a, Sz0 )
⊢ (q1 , a, az0 ) ⇒ abbaaa
⊢ (q1 , ϵ, z0 )
⊢ (q2 , ϵ, z0 )

Dr. Lavanya Selvaganesh CSO322 25 / 32

Theorem
Let G = (V , Σ, S, P) be a context-free grammar. Then the top-down
PDA M described above accepts L(G).

Proof: First, to show L(G) ⊆ L(M).

If x is any string in L(G), then the last step in a leftmost derivation of x
looks like
yAz =⇒ yy ′ = x
where y , y ′ , z are strings of terminals and a typical intermediate step
looks like
yAα =⇒ yy ′ β
where again y and y ′ are strings of terminals for which yy ′ is a prefix of
x and the string β begins with a variable.

Dr. Lavanya Selvaganesh CSO322 26 / 32

Bottom-Up Approach
In this approach, there are opposite counter-parts to both types of
moves in the top-down PDA.
Instead of replacing a variable A on the stack by the right side α of
the production A → α, the PDA removes α from the stack and
replaces it by A, so that the tree is extended upwards.
Example: S → S + T |TT = T ∗ a|a

Dr. Lavanya Selvaganesh CSO322 27 / 32

A CFG to a given PDA

Dr. Lavanya Selvaganesh CSO322 28 / 32

Pumping Lemma for Context-free Languages

Lemma
For any h ≥ 1, a binary tree having more than 2h−1 leaf nodes must
have height greater than h.

Theorem
Let G = (V , Σ, S, P) be a CFG in CNF with a total of p-variables.
Any string u ∈ L(G) with |u| ≥ 2p+1 can be written as u = vwxyz, for
some strings v , w, x, y and z satisfying |wy | > 0 and |wxy | ≤ 2p+1 for
any m ≥ 0, vw m xy m z ∈ L(G).

Dr. Lavanya Selvaganesh CSO322 29 / 32

Pumping Lemma for CFL - Proof
Since the grammar is in Chomsky Normal Form, any derivation
tree for the string u must be a binary tree and since the length of
the string u, |u| ≥ 2p+1 , the height of the tree must be at least
p + 2.
Let us consider a path of maximum length and look at the bottom
position, consisting of a leaf node and the p + 1 nodes above it.
Each of these p + 1 nodes correspond to a variable, and since
there are only p distinct variables, some variable A must appear
twice in this position of the path.
Let x be the portion of u derived from A closest to the leaf and let
t = wxy be the portion of u derived from the other A. If v and z
represent the beginning and ending portions of u, we have
u = vwxyz.
The A closest to the root in this portion of the path is the root of a
binary derivation tree for wxy .

Dr. Lavanya Selvaganesh CSO322 30 / 32

Pumping Lemma for CFL - Proof

Since we began with a path of maximum length, this tree has

height ≤ p + 2 and so |wxy | ≤ 2p+1 . The node containing this A
has two children, both corresponding to variables.
Let B denote the one that is not lying in the max length path i.e. B
is not an ancestor of A (near the leaf), the string of terminals
derived from B does not overlap x.
It follows that either w or y is non-null and hence |wy | > 0.
Finally, S ⇒∗ vAz ⇒ vwAyz ⇒∗ vwxyz.
Hence, we get
S ⇒∗ vAz ⇒ vwAyz ⇒ vw 2 Ay 2 z ⇒ . . . ⇒ vw m Ay m z ⇒∗
vw m xy m z, for any m ≥ 0.

Dr. Lavanya Selvaganesh CSO322 31 / 32

Pumping Lemma for Context-Free Languages

Let L be a CFL. Then there is an integer n so that for any u ∈ L,

satisfying |u| ≥ n, there are strings v , w, x, y , z satisfying

u = vwxyz
where |wy | > 0 , |wxy | ≤ n.
For any m ≥ 0, vw m xy m z ∈ L.

Proof: Obtain a CFG in Chomsky Normal Form that generates

L − {ϵ}. If we let p be the number of variables in the grammar and
n = 2p+1 , the result follows from previous theorem.
Examples
0n 1n 2n and {SS|S ∈ {a, b}∗ } are not CFLs.

Dr. Lavanya Selvaganesh CSO322 32 / 32