Theory of

Computation
Construct Transition table for PDA that
accepts the language a2nbn|n≥1.
Trace PDA for n=3.

L=a2nbn
Finite
controls
Accept / Reject

i/p tape

Stack

Logic: Z0
The Language is as that no.of as’
is twice the no.of bs’.
We push any stack symbol (say Z)
for a pair of as’ and for each b
we pop the symbol (Z) from the
stack

PDA accepting by reaching final state

Working of the PDA
When the pointer reads a and
1 is in the initial state and top symbol of
Lets take any string if the
given language say
stack is Z0 it pushes Z on top of Z0 in the
stack and still at q0

• State = q0 aab
• Stack = Z

Z0

2 When the pointer reads a

The pointer moves to left

and is in the initial state and top

symbol of stack is Z it neither pushes
nor pops from the stack but moves to aab
q1

• State = q1
• Stack =
Z
Z0

3’ 3
When the pointer
reads a and is in q1 state and
aab
top symbol of stack is Z it
neither pushes nor pops but
When the
bounces back to q 0 pointer reads b and is in q1
• State = q0 and top symbol of stack is Z it
pops Z on to the stack and
• Stack = moves to q2
Z0

• State = q2
• Stack =
When the pointer
reads b and is in q2 state and
4’ top symbol of stack is Z it
neither pushes nor pops but
4 aabε
stays at q2

• State = q2
• Stack = When the
Z0 pointer reads ε and is in q2
and top symbol of stack is Z0 it
neither pops nor pushes but
moves on to q3 (Final State)

• State = q3
Reaching the final
state implies that the string • Stack =
is valid and is a part of this Z0

Language
L=a2nbn

Transition Fn (δ)
(q0,a,Z0) = (q0,ZZ0)
(q0,a,Z) = (q1,Z)
(q1,a,Z) = (q0,Z)
(q1,b,Z) = (q2,ε)
(q2,b,Z) = (q2,ε)

(q3,Z0)
acceptance through
Final state
(q2,ε,Z0) =
(q2,ε)
acceptance through
emptying Stack
Tracing PDA translations for n = 3
(q0,a,Z0) = (q0,ZZ0)

1. (q0 ,a,Z0) = (q 0 ,ZZ0) (q0,aa,Z) = (q1,ZZ0)

2. (q0,a,Z) = (q1,Z)
3. (q1,a,Z) = (q0,ZZ) (q1,aaa,Z) = (q0,ZZZ0)
4. (q1 ,b,Z) = (q2,ε)
5. (q1 ,b,Z) = (q2,ε) (q0,aaaa,Z) = (q1,ZZZ0)
6. (q1,ε,Z0) = (q3,Z0)
(q0,aaaaa,Z) = (q0,ZZZ0)

(q0,aaaaaa,Z) = (q1,ZZZZ0)

(q0,aaaaaab,Z) = (q2,ε) |(q2,ZZZZ0)

(q0,aaaaaabb,Z) = (q2,ε) |(q 2,ZZZ0)

(q0,aaaaaabbb,Z) = (q2,ε) |(q 2,ZZ0)

(q0,aaaaaabbbε,Z) = (|q3,Z0) | Final State => accepted

Devika shrouti 21070122516

Ameysingh Yogeshsingh Bayas 2 1070122517
Santhosh Phanitalpak Gandhala 21070122518

Under the guidance of

Dr . Vipin Tiwari