Theory of Computation

Course Code:
CSE1008

By:
Dr. Monali Bordoloi,
Assistant Professor Senior Grade 2
1 SCOPE.
02/07/2025 08:18 AM
 Module 4
Pushdown Automata
(PDA)
Definition, Graphical Notation, Instantaneous Descriptions of PDA-
Acceptance by Final state, Acceptance by empty stack, Deterministic PDA-
CFG to PDA - PDA to CFG

2 07/02/2025
Push Down Automata (PDA)
PDA is the automata that
recognizes a CFL and implements
a CFG.

• Any language acceptable by

FA can also be acceptable by
PDA. PDA also accepts a class
of language that cannot even
be accepted by FA.
• PDA is much more
superior to FA.

• PDA can remember an infinite

amount of information.

• PDA == [  -NFA + “a stack” ]

Push Down Automata (PDA)
“Finite state machine" + "a stack"
Basic Structure of PDA
Read head Stack
Three components − Input tape
Top
1. an input tape: It is divided in many cells or
symbols. The input head is read-only and may
only move from left to right, one symbol at a Push/Pop
time. Finite Control
2. a control unit: The finite control has some

start symbol
pointer which points the current symbol

Bottom/
which is to be read. Output

3. a stack with infinite size.: It is used to store

the items temporarily.
PDA
The stack head scans the top symbol of the stack.

A stack does two operations −

1. Push − a new symbol is added at the top.
2. Pop − the top symbol is read and removed.

A PDA may or may not read an input symbol, but it has to read the top of the stack in
every transition.
 Push Down Automata (PDA)
Formal definition
set of pushdown symbols (which can be pushed and
A PDA P is a 7 tuple:= ( Q,∑,, δ,q0,Z0,F ): popped from the stack)

Q: states of the -NFA • A set of rules that define how the PDA moves
from one state to another based on the current
∑: input alphabet input symbol and the top symbol of the stack.
• The transition function specifies the next state, the
: stack symbols
symbol to be pushed onto the stack (if any), and
δ: transition function the symbol to be popped from the stack (if any).
• The transition function can be represented as a
q0 : start state transition table or a set of transition rules.
Z0 : First stack top symbol Mathematically, it maps Q x {Σ ∪ ∈} x Γ into Q x Γ*
F: Final/accepting states In a given state, the PDA will read the input symbol
and stack symbol (top of the stack), then moves to a
new state, and change the top symbol of the stack.

Acceptance Condition:
The criteria that determine whether the PDA accepts or rejects an input string.
• The PDA accepts an input string if it reaches a final state after consuming all the input symbols and
the stack is empty.
• If the PDA cannot reach a final state or the stack is not empty after consuming all the input
symbols, the input string is rejected.
Push Down Automata (PDA)
A transition in a PDA from a state q1 to state q2, labeled as
a,b → c
 At state q1, if we encounter an input string ‘a’ and top
symbol of the stack is ‘b’, then we pop ‘b’, push ‘c’ on
top of the stack and move to state q2
1 2

Instantaneous Description (ID)

The transition function takes as argument a triple
ID=(q, a, X) where:
(i) q is a state in Q
(ii) a is either an input symbol in ∑ (remaining input string) or a=ɛ
(iii)X is a stack symbol, that is a member of ᴦ or the current stack contents as a string from top
to bottom of the stack.
The output of ID is a finite set of pairs (p, γ) where:
P is a new state
γ is a string of stack symbols that replaces X at the top of the stack

• If γ = ɛ then the stack is popped

• If γ = X then the stack is unchanged
• If γ = YZ then X is replaced by Z and Y is pushed onto the stack
Push Down Automata (PDA)
Turnstile Notation

The "turnstile" notation is used for connecting pairs of ID's that represent one or many moves of a
PDA. The process of transition is denoted by the turnstile symbol " ⊢".

• ⊢ sign describes the turnstile notation and represents one move.

• ⊢* sign describes a sequence of moves.

For example,
(p, b, T) ⊢ (q, w, α)
 While taking a transition from state p to q, the input symbol 'b' is consumed, and the top of the
stack 'T' is represented by a new string α.

If δ(q,a, X)={(p, A)} is a transition, then the following are also true:
(q, a, X ) ⊢ (p,,A)
(q, aw, XB ) ⊢ (p,w,AB)
 Push Down Automata (PDA)
Working of the Transition Function

old state Stack top new Stack top(s)

δ : Q x {Σ ∪ ∈} x  => Q x 
input symbol new state(s)

δ(q,a,X) = {(p,Y), …}
a X Y
1. state transition from q to p q p
2. a is the next input symbol
3. X is the current stack top symbol
inissmm

4. Y is the replacement for X; Y=? Action

erm ini

it is in * (a string of stack symbols) i) Y= Pop(X)

-deetterm

i. Set Y =  for: Pop(X)

ii) Y=X Pop(X)
ii. If Y=X: stack top is unchanged
NNoonn-d

Push(X)
iii. If Y=Z1Z2…Zk: X is
iii) Y=Z1Z2..Zk Pop(X)
popped and is replaced by Y in
Push(Zk)
reverse order (i.e., Z1 will be the
new stack top) Push(Zk-1)
…
Push(Z2)
Push(Z1)
Push Down Automata (PDA)
PDA Acceptability

Final State Acceptability

A PDA accepts a string when, after reading the entire string, the PDA is in a final state.
• From the starting state, we can make moves that end up in a final state with any
stack values.
• The stack values are irrelevant as long as we end up in a final state.

For a PDA (Q, ∑, S, δ, q0, I, F), the language accepted by the set of final states F is −
L(PDA) = {w | (q0, w, I) ⊢* (q, ε, x), q ∈ F}
for any input stack string x.

Empty Stack Acceptability

A PDA accepts a string when, after reading the entire string, the PDA has emptied its
stack.

For a PDA (Q, ∑, S, δ, q0, I, F), the language accepted by the empty stack is −
L(PDA) = {w | (q0, w, I) ⊢* (q, ε, ε), q ∈ Q}
Push Down Automata (PDA)
Example 1
Construct PDA for the language L={, n}
Idea:
• For each 'a' in the input, the PDA pushes an 'a' onto the stack.
• When a 'b' is encountered, the PDA pops an 'a' from the stack, and the state is changed
for the 1st encounter.
• If the PDA reaches the end of the input string and the stack is empty, the string is
accepted.
L={ab,aabb,aaabbb,….} a a b b
Push Down Automata (PDA)
Example 1
Construct PDA for the language L={, n}
Idea:
• For each 'a' in the input, the PDA pushes an 'a' onto the stack.
• When a 'b' is encountered, the PDA pops an 'a' from the stack, and the state is changed
for the 1st encounter.
• If the PDA reaches the end of the input string and the stack is empty, the string is
accepted.
L={ab,aabb,aaabbb,….} a a b b
ID for Transitions
δ(q0, a, ) = (q0, a)
a
Push Down Automata (PDA)
Example 1
Construct PDA for the language L={, n}
Idea:
• For each 'a' in the input, the PDA pushes an 'a' onto the stack.
• When a 'b' is encountered, the PDA pops an 'a' from the stack, and the state is changed
for the 1st encounter.
• If the PDA reaches the end of the input string and the stack is empty, the string is
accepted.
L={ab,aabb,aaabbb,….} a a b b
ID for Transitions
δ(q0, a, ) = (q0, a) a
δ(q0, a, a) = (q0, aa) a
Push Down Automata (PDA)
Example 1
Construct PDA for the language L={, n}
Idea:
• For each 'a' in the input, the PDA pushes an 'a' onto the stack.
• When a 'b' is encountered, the PDA pops an 'a' from the stack, and the state is changed
for the 1st encounter.
• If the PDA reaches the end of the input string and the stack is empty, the string is
accepted.
L={ab,aabb,aaabbb,….} a a b b
ID for Transitions
δ(q0, a, ) = (q0, a)
δ(q0, a, a) = (q0, aa) a
δ(q0, b, a) = (q1, ε)
Push Down Automata (PDA)
Example 1
Construct PDA for the language L={, n}
Idea:
• For each 'a' in the input, the PDA pushes an 'a' onto the stack.
• When a 'b' is encountered, the PDA pops an 'a' from the stack, and the state is changed
for the 1st encounter.
• If the PDA reaches the end of the input string and the stack is empty, the string is
accepted.
L={ab,aabb,aaabbb,….} a a b b
ID for Transitions
δ(q0, a, ) = (q0, a)
δ(q0, a, a) = (q0, aa)
δ(q0, b, a) = (q1, ε)
δ(q1, b, a) = (q1, ε)
Push Down Automata (PDA)
Example 1
Construct PDA for the language L={, n}
Idea:
• For each 'a' in the input, the PDA pushes an 'a' onto the stack.
• When a 'b' is encountered, the PDA pops an 'a' from the stack, and the state is changed
for the 1st encounter.
• If the PDA reaches the end of the input string and the stack is empty, the string is
accepted.
L={ab,aabb,aaabbb,….} a a b b
ID for Transitions
δ(q0, a, ) = (q0, a)
δ(q0, a, a) = (q0, aa)
δ(q0, b, a) = (q1, ε)
δ(q1, b, a) = (q1, ε)
δ(q1, ε, ) = (qf, ε)
Push Down Automata (PDA)
Example 1
Construct PDA for the language L={, n}
Idea:
• For each 'a' in the input, the PDA pushes an 'a' onto the stack.
• When a 'b' is encountered, the PDA pops an 'a' from the stack, and the state is changed
for the 1st encounter.
• If the PDA reaches the end of the input string and the stack is empty, the string is
accepted.
L={ab,aabb,aaabbb,….} a a b b
ID for Transitions
δ(q0, a, ) = (q0, a)
δ(q0, a, a) = (q0, aa)
δ(q0, b, a) = (q1, ε)
δ(q1, b, a) = (q1, ε)
STACK EMPTY!!
δ(q1, ε, ) = (qf, ε) STRING ACCEPTED!!
Push Down Automata (PDA)
Example 1
Construct PDA for the language L={, n}
Idea:
• For each 'a' in the input, the PDA pushes an 'a' onto the stack.
• When a 'b' is encountered, the PDA pops an 'a' from the stack, and the state is changed
for the 1st encounter.
• If the PDA reaches the end of the input string and the stack is empty, the string is
accepted.
L={ab,aabb,aaabbb,….}
ID for Transitions Transition diagram
δ(q0, a, ) = (q0, a)
a, b, a
δ(q0, a, a) = (q0, aa)
δ(q0, b, a) = (q1, ε) 𝑞0 𝑞1ε, 𝑞𝑓
δ(q1, b, a) = (q1, ε) b, a
δ(q1, ε, ) = (qf, ε) a,a

PDA, P = ( Q,∑,, δ,q0,Z0,F ):

= ({q0, q1, qf}, {a,b}, {, a}, δ, q0, , ,, qf)
Push Down Automata (PDA)
Example 1
Construct PDA for the language L={, n}

Check whether the string aaabbb is accepted by the PDA or not.

Transitions
(q0, aaabbb, )
δ(q0, a, ) = (q0, a)
δ(q0, a, a) = (q0, aa)
δ(q0, b, a) = (q1, ε)
δ(q1, b, a) = (q1, ε)
δ(q1, ε, ) = (qf, ε)
Push Down Automata (PDA)
Example 1
Construct PDA for the language L={, n}

Check whether the string aaabbb is accepted by the PDA or not.

Transitions
(q0, aaabbb, ) ⊢ (q0, aabbb, a)
δ(q0, a, ) = (q0, a)
δ(q0, a, a) = (q0, aa)
δ(q0, b, a) = (q1, ε)
δ(q1, b, a) = (q1, ε)
δ(q1, ε, ) = (qf, ε)
Push Down Automata (PDA)
Example 1
Construct PDA for the language L={, n}

Check whether the string aaabbb is accepted by the PDA or not.

Transitions
(q0, aaabbb, ) ⊢ (q0, aabbb, )
δ(q0, a, ) = (q0, a)
⊢ (q0, abbb, aa)
δ(q0, a, a) = (q0, aa)
⊢ (q0, bbb, aaa) δ(q0, b, a) = (q1, ε)
δ(q1, b, a) = (q1, ε)
δ(q1, ε, ) = (qf, ε)
Push Down Automata (PDA)
Example 1
Construct PDA for the language L={, n}

Check whether the string aaabbb is accepted by the PDA or not.

Transitions
(q0, aaabbb, ) ⊢ (q0, aabbb, )
δ(q0, a, ) = (q0, a)
⊢ (q0, abbb, aa)
δ(q0, a, a) = (q0, aa)
⊢ (q0, bbb, aaa) δ(q0, b, a) = (q1, ε)
δ(q1, b, a) = (q1, ε)
δ(q1, ε, ) = (qf, ε)
Push Down Automata (PDA)
Example 1
Construct PDA for the language L={, n}

Check whether the string aaabbb is accepted by the PDA or not.

Transitions
(q0, aaabbb, ) ⊢ (q0, aabbb, )
δ(q0, a, ) = (q0, a)
⊢ (q0, abbb, aa)
δ(q0, a, a) = (q0, aa)
⊢ (q0, bbb, aaa) δ(q0, b, a) = (q1, ε)
⊢ (q1, bb, aa) δ(q1, b, a) = (q1, ε)
δ(q1, ε, ) = (qf, ε)
Push Down Automata (PDA)
Example 1
Construct PDA for the language L={, n}

Check whether the string aaabbb is accepted by the PDA or not.

Transitions
(q0, aaabbb, ) ⊢ (q0, aabbb, )
δ(q0, a, ) = (q0, a)
⊢ (q0, abbb, aa)
δ(q0, a, a) = (q0, aa)
⊢ (q0, bbb, aaa) δ(q0, b, a) = (q1, ε)
⊢ (q1, bb, aa) δ(q1, b, a) = (q1, ε)
⊢ (q1, b, a)
δ(q1, ε, ) = (qf, ε)
⊢ (q1, , )
Push Down Automata (PDA)
Example 1
Construct PDA for the language L={, n}

Check whether the string aaabbb is accepted by the PDA or not.

Transitions
(q0, aaabbb, ) ⊢ (q0, aabbb, )
δ(q0, a, ) = (q0, a)
⊢ (q0, abbb, aa)
δ(q0, a, a) = (q0, aa)
⊢ (q0, bbb, aaa) δ(q0, b, a) = (q1, ε)
⊢ (q1, bb, aa) δ(q1, b, a) = (q1, ε)
⊢ (q1, b, a)
δ(q1, ε, ) = (qf, ε)
⊢ (q1, , )
⊢ (qf, )

As the stack is empty and the input string is consumed totally, the string aaabbb is
accepted by the PDA.
Push Down Automata (PDA)
Example 2
Construct PDA for the language Lw = {w | w is in (0+1)*}. Check whether the string 0110
is accepted by the PDA or not.
ID:
δ(q0,0, Z0)={(q0,0Z0)} First symbol push on stack
δ(q0,1, Z0)={(q0,1Z0)}
δ(q0,0, 0)={(q0,00)} Grow the stack by pushing new symbols on top of old
δ(q0,0, 1)={(q0,01)} (w-part)
δ(q0,1, 0)={(q0,10)}
δ(q0,1, 1)={(q0,11)}
δ(q0, , 0)={(q1, 0)} Switch to popping mode, nondeterministically
(boundary between w and wR)
δ(q0, , 1)={(q1, 1)}
δ(q0, , Z0)={(q1, Z0)}
δ(q1,0, 0)={(q1, )}
Shrink the stack by popping matching symbols (wR-part)
δ(q1,1, 1)={(q1, )} Enter acceptance state
δ(q , , Z )={(q , Z )}
PDA1
for0 Lw=2(Q,∑,
0
, δ,q0,Z0,F )
= ( {q0, q1, q2},{0,1},{0,1,Z0},δ,q0,Z0,{q2})
Push Down Automata (PDA)
Example 2
Construct PDA for the language Lw = {w | w is in (0+1)*}. Check whether the string 0110
is accepted by the PDA or not.
0, Z0/0Z0
Transition diagram This would be a non-deterministic PDA
1, Z0/1Z0
0, 0/00
Grow stack 0, 1/01
1, 0/10 0, 0/  Pop stack for matching symbols
1, 1/11 1, 1/ 

q0 q1 q2
, Z0/Z0
, Z0/Z0 , Z0/Z0
, 0/0
, 1/1 Go to acceptance
Switch to popping mode
Transition table
Push Down Automata (PDA)
Example 2
Construct PDA for the language Lw = {w | w is in (0+1)*}. Check whether the string 0110
is accepted by the PDA or not.

State Input Stack Transition

0, Z0/0Z0
q0 0110 Z0 0, Z0/0Z0 1, Z0/1Z0
0, 0/00
q0 110 0 1,0/10 0, 1/01
q0 10Z0 , 1/1 1, 0/10
0, 0/ 
1, 1/11
1, 1/ 
q1 10 10Z0 1,1/
q0 q1 q2
q1 0 0Z0 0,0/ , Z0/Z0
, Z0/Z0 , Z0/Z0
, 0/0
q1 Z0 , Z0/Z0 , 1/1
q2 Z0
Push Down Automata (PDA)
Example 2
Construct PDA for the language Lw = {w | w is in (0+1)*}. Check whether the string 0110
is accepted by the PDA or not.
How does the PDA for Lw work on input 1111?
0, Z0/0Z0
All moves made by the NPDA 1, Z0/1Z0
(q0,1111,Z0) Arrows represent move ⊢ relation 0, 0/00
0, 1/01
Path dies… 1, 0/10
(q0,111,1Z0) (q1,1111,Z0) 0, 0/ 
1, 1/11
1, 1/ 

Path dies… q0 q1 q2
(q0,11,11Z0) (q1,111,1Z0) , Z0/Z0
, Z0/Z0 , Z0/Z0
, 0/0
(q0,1,111Z0) (q1,11,11Z0) , 1/1

(q1,1,1Z0)
(q0,,1111Z0) (q1,1,111Z0) Acceptance by final state:
= empty input AND final state
(q1, ,Z0)
(q1, ,1111Z0) (q1, ,11Z0)
Path dies… Path dies…
(q2, ,Z0)
A sequence of moves (a computation):
(q0,1111,Z0) ⊢ (q0,111,1Z0) ⊢ (q0,11,11Z0) ⊢ (q1,11,11Z0) ⊢ (q1,1,1Z0) ⊢ (q1, ,,Z0) ⊢ (q2,
,,Z0)
Push Down Automata (PDA)
Example 2
Construct PDA for the language Lw = {w | w is in (0+1)*}. Check whether the string 0110
is accepted by the PDA or not.
How does the PDA for Lw work on input 01?
0, Z0/0Z0
1, Z0/1Z0
0, 0/00
0, 1/01
1, 0/10
0, 0/ 
1, 1/11
1, 1/ 

q0 q1 q2
, Z0/Z0
, Z0/Z0 , Z0/Z0
, 0/0
, 1/1
Push Down Automata (PDA)
Example 3
Construct PDA for the language L={0n1m0n | m, n>=1}

Check whether the string 0011100 is accepted by the PDA or not.

Idea:
Here, n number of 0's are followed by any number of 1's
followed by n number of 0's. Push all 0's onto the stack
while encountering the first 0's. Then if we read 1, just
do nothing. Then read 0, and on each read of 0, pop one
0 from the stack.

ID:
• δ(q0, 0, Z) = δ(q0, 0Z)
• δ(q0, 0, 0) = δ(q0, 00)
• δ(q0, 1, 0) = δ(q1, 0)
• δ(q0, 1, 0) = δ(q1, 0)
• δ(q1, 0, 0) = δ(q1, ε)
• δ(q0, ε, Z) = δ(q2, Z)

PDA = ({q0, q1, q2}, {0, 1}, {0, Z}, δ, q0, Z, {q2})
Push Down Automata (PDA)
Example 3
Construct PDA for the language L={0n1m0n | m, n>=1}

Check whether the string 0011100 is accepted by the PDA or not.

Transition diagram

Draw YOURSELF!!

δ(q0, 0011100, Z) ⊢ δ(q0, 011100, 0Z) ID:

⊢ δ(q0, 11100, 00Z) • δ(q0, 0, Z) = δ(q0, 0Z)
⊢ δ(q0, 1100, 00Z) • δ(q0, 0, 0) = δ(q0, 00)
⊢ δ(q1, 100, 00Z)
• δ(q0, 1, 0) = δ(q1, 0)
⊢ δ(q1, 00, 00Z)
⊢ δ(q1, 0, 0Z)
• δ(q0, 1, 0) = δ(q1, 0)
⊢ δ(q1, ε, Z) • δ(q1, 0, 0) = δ(q1, ε)
⊢ δ(q2, Z) • δ(q0, ε, Z) = δ(q2, Z)
ACCEPT
Push Down Automata (PDA)
Example 4
Construct PDA for the language L={, n}

Check whether the string aaabbbbbb is accepted by the PDA or not.

Idea:
n number of a's should be followed by 2n number of b's. Hence, if a single ‘a’ is read, push two
a's onto the stack. As soon as ‘b’ is read, for every single 'b' only one 'a' should get popped from
the stack.

ID:
• δ(q0, a, Z) = (q0, aaZ) Transition diagram
• δ(q0, a, a) = (q0, aaa)
• δ(q0, b, a) = (q1, ε) Draw YOURSELF!!
• δ(q1, b, a) = (q1, ε)
• δ(q1, ε, Z) = (q2, ε)

PDA = ({q0, q1, q2}, {a, b}, {a, Z}, δ, q0, Z, {q2})
Push Down Automata (PDA)
Example 4
Construct PDA for the language L={, n}

Check whether the string aaabbbbbb is accepted by the PDA or not.

Idea:
n number of a's should be followed by 2n number of b's. Hence, if a single ‘a’ is read, push two
a's onto the stack. As soon as ‘b’ is read, for every single 'b' only one 'a' should get popped from
the stack.
δ(q0, aaabbbbbb, Z) ⊢ δ(q0, aabbbbbb, aaZ)
⊢ δ(q0, abbbbbb, aaaaZ)
⊢ δ(q0, bbbbbb, aaaaaaZ)
⊢ δ(q1, bbbbb, aaaaaZ)
⊢ δ(q1, bbbb, aaaaZ)
⊢ δ(q1, bbb, aaaZ)
⊢ δ(q1, bb, aaZ)
⊢ δ(q1, b, aZ)
⊢ δ(q1, ε, Z)
⊢ δ(q2, ε)
ACCEPT
Push Down Automata (PDA)
Example 5
Construct the transition diagram of the PDA for the language of balanced parenthesis.

Pop stack for ∑ = { (, ) }

matching symbols G= {Z0, ( }
Grow stack Q = {q0,q1,q2}

(, Z0 / ( Z0
(, ( / ( ( ), ( / 

q0 q1 q2
, Z0 / Z0 ), ( /  , Z0 / Z0
, Z0 / Z0 Go to acceptance (by final state)
Switch to when you see the stack bottom symbol
popping mode (, ( / ( (
(, Z0 / ( Z0

To allow adjacent
blocks of nested paranthesis
Push Down Automata (PDA)
Example 5
Construct the transition diagram of the PDA for the language of balanced parenthesis.

Another PDA design

∑ = { (, ) }
(,Z0 / ( Z0 G= {Z0, ( }
(,( / ( ( Q = {q0,q1}
), ( / 

start ,Z0/ Z0
q0 q1
,Z0/ Z0
ACCEPTANCE BY FINAL STATE
Push Down Automata (PDA)
Example 5
Construct the PDA for the language of balanced parenthesis.

PDA that accepts by final state An equivalent PDA that accepts by an empty stack

(,Z0 / ( Z0
P F: PN: (, ( / ( (
(,Z0 / ( Z0
(,( / ( ( ), ( / 
), ( /  ,Z0 / 

,Z0/ Z0 start
start
q0 q1 q0
,Z0/ Z0 ,Z0/ Z0

How will these two PDAs work on the input: ( ( ( ) ) ( ) ) ( )

PDA - Equivalence of Language Definitions

PDAs accepting by final state and empty stack are equivalent

Theorem:

Proof by Conversions:
(PN==> PF) For every PN, there exists a PF s.t. L(PF)=L(PN)

(PF==> PN) For every PF, there exists a PN s.t. L(PF)=L(PN)

PDA - Equivalence of Language Definitions
Creating an Equivalent PDA Accepting by Empty Stack from a PDA Accepting by
Final State
PDA - Equivalence of Language Definitions
Creating an Equivalent PDA Accepting by Empty Stack from a PDA Accepting by
Final State
Example:
PDA - Equivalence of Language Definitions
Creating an Equivalent PDA Accepting by Empty Stack from a PDA Accepting by
Final State
Example:
PDA - Equivalence of Language Definitions
Creating an Equivalent PDA Accepting by Final State from a PDA Accepting by
Empty Stack
PDA - Equivalence of Language Definitions
Creating an Equivalent PDA Accepting by Final State from a PDA Accepting by
Empty Stack
PDA - Equivalence of Language Definitions
Creating an Equivalent PDA Accepting by Final State from a PDA Accepting by
Empty Stack

Example 1 :

What is the language of this PDA??

PDA - Equivalence of Language Definitions
Creating an Equivalent PDA Accepting by Final State from a PDA Accepting by
Empty Stack

Example 2 : Let us design a PDA which processes strings of 0's & 1's and accepts, if the
number of 0's is equal to the number of 1's. We shall use two stack symbols A and B to
count the difference between number of 0's seen so far and the number of 1’s.
0, Z | AZ
0, Z | AZ
0, A | AA
0, A | AA
1, Z | BZ
1, Z | BZ
1, B | BB
1, B | BB
0, B | ε
0, B | ε
1, A | ε
1, A | ε
ε, Z | ε
ε, Z | ε
ε, Z | ZX ε, X | ε
Equivalence of PDA and CFG

Grammar PDA by PDA by

CFG empty stack Final state

1. CFL
2. Languages accepted by final state PDA
Same
3. Languages accepted by empty stack PDA

• If a grammar G is context-free, we can build an equivalent nondeterministic PDA that accepts the
language produced by the CFG G. A parser can be built for the grammar G.

• Also, if P is a PDA, an equivalent CFG G can be constructed where L(G) = L(P)

CFG to PDA
Main idea:
The PDA simulates the leftmost
Grammar PDA by derivation on a given w, and upon
consuming it fully it either arrives at
CFG empty stack acceptance (by empty stack) or non-
acceptance.

Steps:
1. Push the right-hand side of the production onto the stack, with the
leftmost symbol at the stack top
2. If stack top is the leftmost variable, then replace it by all its productions
(each possible substitution will represent a distinct path taken by the
non-deterministic PDA)
3. If stack top has a terminal symbol, and if it matches with the next
symbol in the input string, then pop it

State is inconsequential (only one state is needed)

 CFG to PDA
Formal construction of PDA from CFG
Note: Initial stack symbol (S)
Given: G= (V,T,P,S) same as the start variable
in the grammar
Output: PN = ({q}, T, V U T, δ, q, S)
δ:
After:
Before: For all A  V , add the following transition(s) in the PDA:
A δ(q,  ,A) = { (q, ) | “A ==>”  P} 

…
…

Before: For all a  T, add the following After: a…

transition(s) in the PDA:
a a pop
δ(q,a,a)= { (q,  ) }
…

…
CFG to PDA
Example 1: 1,1 / 
0,0 / 
Convert the grammar CFG to a PDA ,A / 01
G = ( {S,A}, {0,1}, P, S) ,A / A1
,A / 0A1
P: ,S / 
S ==> AS | ,S / AS

A ==> 0A1 | A1 | 01
,S / S
q
The equivalent PDA is given by:
P= ({q}, {0,1}, {0,1,A,S}, δ, q, S)
where δ is defined by:
δ(q, , S) = { (q, AS), (q, )}
δ(q, , A) = { (q,0A1), (q,A1), (q,01) }
δ(q, 0, 0) = { (q, ) }
δ(q, 1, 1) = { (q, ) }

How will the PDA check the acceptance of a string??

 CFG to PDA
1,1 / 
How will the PDA check the acceptance of the string 0011?? 0,0 / 
,A / 01
PDA (δ): Leftmost deriv.: ,A / A1
δ(q,  , S) = { (q, AS), (q,  )} ,A / 0A1
δ(q,  , A) = { (q,0A1), (q,A1), (q,01) } ,S / 
δ(q, 0, 0) = { (q,  ) } S => AS ,S / AS
δ(q, 1, 1) = { (q,  ) } => 0A1S
=> 0011S ,S / S

=> 0011 q

Stack moves (shows only the successful path):

0 0
A A 1 1
A 1 1 1 1 1 Accept by
S S S S S S S S
empty stack
0 0 1 1 

S =>AS =>0A1S =>0011S => 0011

CFG to PDA
Example 2:
Convert the grammar CFG to a PDA
G = ({P}, {0,1}, {P  0P0, P  1P1, P  }, P)

The equivalent PDA is given by:

A= ( {q}, {0,1}, {0,1,P}, δ,, q, P)
where δ is defined by:
δ (q, ,P) = { (q,0P0), (q,1P1), (q, ) }
δ(q,0,0) = { (q, ) }
δ (q,1,1) = { (q, ) }

 Check the acceptance of the string 0110.

Thus, G represents the grammar that generates palindromes

CFG to PDA
Example 3:
Convert the grammar CFG to a PDA
E→E+E
E →id

The equivalent PDA is given by:

P= ({q}, {+,id},{E,+,id},δ, q, E}
where δ is defined by:
δ(q,ε, E)={(q, E+E), (q,id)}
δ(q, id,id)={(q, ε)}
δ(q,+,+)={(q, ε)}
CFG to PDA
Example 4
Convert the grammar CFG to a PDA
S→0S1|A
A →1A0|S|ε

The equivalent PDA is given by:

P= ({q}, {0, 1},{S,A,0,1}, δ, q, S}
where δ is defined by:
δ(q,ε, S)={(q, 0S1), (q, A)}
δ(q,ε, A)={(q, 1A0), (q, S), (q,ε)}
δ(q, 0,0)={(q, ε)}
δ(q,1,1)={(q, ε)}
CFG to PDA
Practice Questions:
Construct a PDA from the grammar CFG
5. S→0BB|A
B →0S|1S|0

6. E→E+E|E*E|(E)|I
I →a|b|Ia|Ib|I0|I1

7. E→E+T | T
T →T*F |F
F →(E) | I
I → a | b | Ia | Ib | I0 | I1
PDA to CFG
We have, P = (Q,T, Γ, , q0, Z0, F). Construct G=(V,T,P,S)
where V consists of
1. The special symbol S, which is the start symbol and
2. All symbols of the form [pXq] where p and q are states in Q and X is a stack
symbol in Γ.
Main idea: Reverse engineer the productions from transitions.
• We assume the PDA accepts a language L by an empty stack.

a) RULE 1: Start Symbol Production: For all states p, G has the production
S→[q0Z0p]
Since, [q0,w, Z0]├*(p,ε,ε). This production says that the start symbol S will generate all strings w that
cause p to empty its stack, starting in its initial ID.
• If the PDA has n states, there will be n productions originating from the start symbol S.

b) RULE 2: Handling Transitions with Empty Stack Operation

If we have, δ(q,a,Z0) = { (p,  ) } where (q, p) ∈ Q, a ∈ Σ, and Z0 ∈ Γ, a production rule is added to
the CFG as - [qZ0p] a
This rule handles cases where the PDA reads the symbol “a” and pops the stack without pushing
anything.
If a= ϵ, i.e. we have, δ(q, ϵ, Z0) → (p, ϵ), then add [qZ0p] 
PDA to CFG
c) RULE 3: Handling Transitions with Stack Operations:
If we have, δ(q,a,Z) => (p, Y1Y2Y3…Yk), a production rule is added for each combination of
intermediate states q1,q2, ... ,qk as:
[qZp] => a[pY1q1] [q1Y2q2] [q2Y3q3]… [qk-1Ykqk]
This rule addresses scenarios where the PDA pushes multiple symbols onto the stack in response to
an input symbol, i.e. stack top symbol Z is popped and replaced with a sequence of k variables when
“a” is consumed.

Example 1: Balanced Parenthesis:

To avoid confusion, we will use b=“(“ and e=“)”
PN : ( {q0}, {b,e}, {Z0,Z1}, δ, q0, Z0 ) 0. S => [q0Z0q0]
1. [q0Z0q0] => b [q0Z1q0] [q0Z0q0]
1. δ(q0,b,Z0) = { (q0,Z1Z0) } 2. [q0Z1q0] => b [q0Z1q0] [q0Z1q0]
2. δ(q0,b,Z1) = { (q0,Z1Z1) } 3. [q0Z1q0] => e
3. δ(q0,e,Z1) = { (q0,  ) } 4. [q0Z0q0] => 
4. δ(q0,  ,Z0) = { (q0,  ) }
Let A=[q0Z0q0]
Simplifying,
Let B=[q0Z1q0]

If you were to directly write a CFG: 0. S => b B S | 

0. S => A
1. B => b B B | e
1. A => b B A
S => b S e S |  2. B => b B B
3. B => e
4. A => 
PDA to CFG
Example 2: Construct a CFG from PDA such that the PDA’s IDs are as follows,
δ(q0,a,z0)→(q0,z1z0)
δ(q0,a,z1)→(q0,z1z1) Rules:
δ(q0,b,z1)→(q1,λ) 1. For all states p, S→[q0Z0p]
δ(q1,b,z1)→(q1,λ) 2. If δ(q,a,Z0) = { (p,  ) }
δ(q1,b,z0)→(q1,z2z0) [qZ0p] a
δ(q1,c,z2)→(q2,λ) If δ(q, ,Z0) = { (p,  ) }
δ(q2,λ,z0)→(q2,λ) [qZ0p] 
This PDA has three states: q0, q1, and q2. 3. If δ(q,a,Z) => (p, Y1Y2Y3…Yk)
[qZp] => a[pY1q1] [q1Y2q2] [q2Y3q3]… [qk-1Ykqk]
1. As PDA has three states: q0, q1, and q2

δ(q0,b,z1)→(q1,λ)
2 [qoz1 q1] → b δ(q1,b,z1)→(q1,λ)
[q1z1 q1] → b δ(q1,c,z2)→(q2,λ)
[q1z2 q2] → c δ(q2,λ,z0)→(q2,λ)
[q2z0 q2] → /λ
3. [qoz0 q0] → a [qoz1 q0] [qoz0 q0] δ(q0,a,z0)→(q0,z1z0)
[q0z1 q0] → a [qoz1 q0] [qoz1 q0] δ(q0,a,z1)→(q0,z1z1)
[q1z0q1] → b [q1z2 q1] [q1z2 q1] δ(q1,b,z0)→(q1,z2z0)
 PDA to CFG
Practice Problems:
Example 3: Construct a CFG from PDA such that the PDA’s IDs are as follows,
δ(q0,a,z0)→(q1,z1z0) Rules:
δ(q0,b,z0)→(q1,z2z0) 1. For all states p, S→[q0Z0p]
δ(q1,a,z1)→(q1,z1z1) 2. If δ(q,a,Z0) = { (p,  ) }
δ(q1,b,z1)→(q1,λ) [qZ0p] a
δ(q1,b,z2)→(q1,z2z2)
If δ(q, ,Z0) = { (p,  ) }
δ(q1,λ,z0)→(q1,λ)
[qZ0p] 
3. If δ(q,a,Z) => (p, Y1Y2Y3…Yk)
[qZp] => a[pY1q1] [q1Y2q2] [q2Y3q3]… [qk-1Ykqk]
Example 4: Construct a CFG from PDA such that the PDA’s IDs are as follows,
δ(q,0, Z0)={(q,X Z0 ) }
δ(q,0, X)={(q,XX ) }
δ(q,1, X)={(q,X ) }
δ(q,ε, X)={(p, ε ) }
δ(p, ε, X)={(p, ε ) }
δ(p,1, X)={(p,XX ) }
δ(p,1, Z0)={(p, ε ) }
 PDA and CFG

Build a PDA Construct (indirect)

CFG from PDA
Two ways to
build a CFG
Derive CFG directly (direct)

Derive a CFG Construct

PDA from CFG (indirect)
Two ways
to build a
PDA
Design a PDA directly (direct)
Deterministic PDA
A DPDA is a pushdown automaton in which each configuration of the DPDA has at
most one valid move.
• The DPDA has a single, deterministic choice for the next action, based on the current state, the
input symbol, and the top of the stack.
Formally, a PDA is deterministic if and only if:
δ(q,a,X) has at most one member for any a  ∑ U {}
 If δ(q,a,X) is non-empty for some a∑, then δ(q, ,X) must be empty.

Properties of DPDA:
Language Class: DPDAs can recognize a subset of context-free languages called deterministic
context-free languages (DCFLs).

Uniqueness of Transition: At every step, based on the current input symbol and the top of the
stack, the DPDA can perform at most one action (either push, pop, or read the input).

More Restrictive: DPDAs are less powerful than NPDAs because they cannot recognize all
context-free languages. For example, the language L={ ∣n≥1} cannot be recognized by a DPDA,
but an NPDA can recognize it.
Deterministic PDA
Example 1: The language L={|n≥1} is a deterministic CFL.

Proof: The PDA M=({q0,q1,q2,q3},{a,b},{0,1},δ,q0,Z,{q3}) with

δ(q0,a,Z)={(q1,1Z)},
δ(q1,a,1)={(q1,11)},
δ(q1,b,1)={(q2,λ),
δ(q2,b,1)={(q2,λ)},
δ(q2,λ,Z)={(q3,λ)}
accepts the given language.

It satisfies the conditions for being deterministic.

Note
This machine DOES have λ transitions.
 The key point is that there is still only one choice (because of what is sitting on the top of the
stack). In that sense, it is not merely a “free ride” transition.
Deterministic PDA
Example 2: ODD-LENGTH PALINDROMES L=wcwR

a,Z0 /aZ0
b,Z0 /bZ0
a,b /ab
b,a /ba a,a /ε
a,a /aa b,b/ε
b,b /bb
ε,Z0/Z0

q1 q2 q3

c,Z0 /Z0
c,a /a
c,b /b
 Non-Deterministic PDA
Example 1 : EVEN-LENGTH PALINDROMES L=wwR

a,Z0 /aZ0
b,Z0 /bZ0
a,b /ab
b,a /ba a,a /ε
a,a /aa b,b/ε
b,b /bb
ε,Z0/Z0

q1 q2 q3

ε, Z0 /Z0
ε, a /a
ε, b /b
It contains these transitions:
δ(q0,a,a)={(q0,aa)}
δ(q0, ε ,a)={(q1,a)}
This violates our conditions for determinism. << Do you see why? >>
 Non-Deterministic PDA
An NPDA is a PDA where multiple transitions may be possible from a given configuration.
• At any point in time, the NPDA can choose from several possible actions based on the current state,
input symbol, and the stack's top symbol.
• The machine accepts the input if any sequence of transitions leads to an accepting state.

Properties of NPDA:
 Language Class: NPDAs can recognize all context-free languages (CFLs). Every NPDA can be
converted to a CFG and vice versa.

 Multiple Transitions: NPDAs allow non-deterministic behavior, meaning they can "guess" the
correct sequence of moves to reach an accepting state.

 More Powerful: NPDAs are strictly more powerful than DPDAs because they can recognize
languages that are not deterministic, like L={ ∣m,n≥1}.
Non-Deterministic PDA
Example 2:
An NPDA can recognize the language { ∣n≥1} which consists of strings with equal numbers of a's,
and b's.

States: Q={q0,q1,q2,qf}
Input Alphabet: Σ={a, b, c}
Stack Alphabet: Γ={a,Z0}
Transitions: The NPDA works by:
 Pushing a's onto the stack while reading a.
 Popping a's from the stack while reading b’s.
 Ensuring that the stack is empty when reading the c’s.

The transitions may involve nondeterministic choices between reading input symbols or
popping symbols from the stack.
Comparison between DPDA and NPDA

Key Differences between DPDA and NPDA:

1. Deterministic (DPDA): Every step is predetermined, and only one path through the automaton
is valid.
2. Nondeterministic (NPDA): The machine can make several guesses, and as long as one guess
leads to an accepting state, the input is accepted.
Comparison between DPDA and NPDA
Lwcwr Lwwr

Regular languages D-PDA

Non-deterministic PDA

 NPDA is a more powerful model that can recognize all context-free languages, while DPDA can
only recognize a subset of these languages (deterministic CFLs).

 Regular languages are simpler and can be recognized by finite automata without the need for
stack memory.
 Simplification of CFG
CFG may contain redundant rules,
unreachable symbols, or
unnecessary complexities
These may not be required to derive a string supported by the language of the grammar

Simplifying a CFG helps in reducing its size while preserving the generated language, making
parsing more efficient.
• Efficient Parsing: Smaller grammars require fewer computations.
• Better Understanding: Removing redundant parts makes it easier to analyze.
• Optimization: Improved computational efficiency in compilers and language processing.
Simplification of CFG
1. Removal of Useless Symbols/Production

 If a symbol does not exist on the right-hand side of the production rule and does not participate in
the derivation of any string, that symbol is considered a useless symbol. Similarly, if a variable
does not participate in the derivation of any string, it is useless.

 The productions that can never take part in derivation of any string, are called useless
productions.

Example: T → xxY | xbX | xxT

X → xX
Y → xy | y
Z → xz

 The variable ‘Z’ will never occur in any string’s derivation. Thus, the production Z → xz is
useless. Therefore, eliminate it.
All the other productions would be written in a way that the variable Z can never reach from
the ‘T’ starting variable.

 Production X → xX would also be useless because it cannot terminate it in any way.

 If it never terminates, it can never produce a string. Thus, such a production can not
participate in any derivation.
Simplification of CFG
1. Removal of Useless Symbols/Production
Example: T → xxY | xbX | xxT
X → xX
Y → xy | y
Z → xz

• To remove useless productions, first find all the variables which will never lead to a
terminal string.
• Then remove all the productions in which the variable occurs.

Here, The X in the production X → xX will never lead to a terminal string

The modified CFG is: T → xxY | | xxT
Y → xy | y
Z → xz

• Identify all the symbols/variables that can never be reached from the starting variable
• Then remove all the productions in which the variable occurs.

Here, Z is unreachable from T.

The modified CFG is: T → xxY | | xxT
Y → xy | y
Simplification of CFG
2. Elimination of ε Production

Productions of type 'A → ε' (also known as null/lambda productions)

It is possible for a grammar to contain null productions and yet not produce an empty
string. There need not be a production of A → ε if it is not in the L language.

To remove null productions, we first have to find all the nullable variables.
 For all the productions of type A → ε, ‘A’ is a nullable variable.
 For all the productions of type B …where all s are nullable variables, ‘B’ is also a
nullable variable.

Construction of the null production free grammar.

For all the productions in the original grammar,
 Add the original production.
 Add all the combinations of the production that can be formed by replacing the
nullable variables in the production by ε.
 If all the variables on the RHS of the production are nullable, then we do not
add the production to the new grammar.
Simplification of CFG
2. Elimination of ε Production

Example: S → ABA
A → 0A | ε
B → 1B | ε

Start with the first production. Add the first production as it is.
S → ABA

Create all the possible combinations that can be formed by replacing the nullable variables with ε.
Here, while removing ε production, the rules A → ε and B → ε would be deleted. To
preserve the CFG’s meaning, place ε at the RHS whenever A and B appear.

Let us take: S → ABA

If the first A at RHS is ε. Then, S → BA
Similarly, if the last A in RHS = ε. Then, S → AB
If B = ε, then S → AA
If B and A are ε, then S → A
If both A is replaced by ε, then S → B

Now,
S → AB | BA | AA | A | B
Simplification of CFG
2. Elimination of ε Production

Example: S → ABA
A → 0A | ε
B → 1B | ε

Start with the first production. Add the first production as it is.
S → ABA
Now,
S → AB | BA | AA | A | B

Now, let us consider

A → 0A
If we place ε at RHS for A, then A → 0
Thus, A → 0A | 0

Similarly, B → 1B | 1

Rewrite the CFG collectively with removed ε production as:

S → AB | BA | AA | A | B
A → 0A | 0
B → 1B | 1
Simplification of CFG
3. Removal of Unit Production
Unit productions: The productions that produces a non-terminal from a non-terminal, say A B
Steps to remove unit productions:
Step 1: To remove A → B, add production A → x to the grammar rule whenever B → x occurs in
the grammar. [x ∈ Terminal, x can be Null]
Step 2: Delete A → B from the grammar.
Step 3: Repeat from step 1 until all unit productions are removed.
Example: S → 0A | 1B | C
A → 0S | 000
B → 11 | A
C → 01

S -> C denotes a unit production. However, before we remove S -> C, we must consider what C
provides. As a result, we can add a rule to S.
S → 0A | 1B | 01
Similarly, B → A is a unit production; we can change it as
Now solve the 3
B → 11 | 0S | 000
As a result, we can finally write CFG without unit production as practice questions of
S → 0A | 1B | 01 CFG to PDA!!
A → 0S | 000
B → 11 | 0S | 000
C → 01
By: Dr. Monali Bordoloi, Asst. Prof. Sr. Gra 74 02/07/2025 08:20 AM
de 1, VIT-AP