Established as per the Section 2(f) of the UGC Act, 1956
Approved by AICTE, COA and BCI, New Delhi
Lecture 31.2
Push Down Automata(PDA)
S c h o o l o f C o m p u t i n g a n d I n f o r m a t i o n Te c h n o l o g y
D r. P a r t h a s a r a t h y G
P a r t h a s a r a t h y. g @ re v a . e d u . i n
AY:2020-2021
OUTLINE
Recap of Previous Lecture
Topic of the Lecture
Objective and Outcome of Lecture
Lecture Discussion
•Problem Statement
• Solution to the Problem
• Transition Diagram
• Definition of PDA
• Moves
• Transition Function (δ)
•
Push Down Automata
Recap of Previous Lecture
RECAP OF PREVIOUS LECTURE
Introduction to Push Down Automata
• Introduction
Course
• Description
Formal Definition of PDA
• Acceptance of Final State
• Acceptance by Empty Stack
• Example
ID
• Applications
• Summary
Push down Automata
To p i c o f t h e L e c t u r e
TOPIC OF THE LECTURE
•
• Problem Statement
• Solution to the Problem
Push Down
• Transition Diagram
Automata
EXAMPLE(3) • Definition of PDA
• Moves
• Transition Function (δ)
Push Down Automata
Objective and Outcome of Lecture
OBJECTIVE AND OUTCOME OF LECTURE
• Explain the structure and representation of
Lecture Push Down Automata to identify the
Objective language L={ aibjck | i,j,k>0, i=j or i=k} that it
accept or reject.
Lecture • Identify the language L={ aibjck | i,j,k>0, i=j
Outcome or i=k} accepted or rejected by a PDA.
Push Down Automata
PUSH DOWN AUTOMATA
Problem Def. : Construct a PDA to accept a given language L by
final state where L={ aibjck | i,j,k>0, i=j or i=k}
Solution: Nature of the language will be
1. Atleast L could have one a, b, c due to condition i,j,k >0.
2. There is existence of equal number of a’s and b’s (or) equal number of a’a
and c’s
w=abbc ϵ L due to i=k, aabc ϵ L because number of a’s not equal to c’s i=k
Logic: case i: To check i=j , push all the a’s into the stack when b is encounter
then pop the stack, until c is encounter then c is checked with top of the stack
z0 , then it comes to accepting state.
PUSH DOWN AUTOMATA
Problem Def. : Construct a PDA to accept a given language L by
final state where L={ aibjck | i,j,k>0, i=j or i=k}
Logic: case ii: To check i=k , push all the a’s into the stack when b is encounter
then keep as it is until c is encounter, when c is encounter pop the a’s and
compare until to reach the accepting state.
L={ aibjck | i,j,k>0, i=j or i=k}
a, a / aa
a, Z0 / aZ0 b,a/ϵ
q1 q2
q0 ϵ, Z0 / Z0
b,a/ϵ
b,a/a
ϵ, Z0 / Z0
q3 q4 q5
c,a/ϵ
b,a/a c,a/ϵ
PUSH DOWN AUTOMATA L={ aibjck | i,j,k>0, i=j or i=k}
P := ( Q,∑, , δ,q0,Z0,F )
= ( {q0, q1, q2, q3, q4, q5},{a,b,c},{a,Z0},δ,q0,Z0,{q2,q5})
1. δ(q0,a, Z0)={(q0,aZ0)} First symbol push on stack
2. δ(q0,a, a)={(q0,aa)} Grow the stack by pushing
3. δ(q0, b, a )={(q1, ) ,(q3,a)} Switch to popping mode or protect the stack
Shrink the stack by popping matching
4. δ(q1, b, a )={(q1, )}
5. δ(q1,c, Z0)={(q2,Z0)} Enter acceptance state if i=j
6. δ(q2,c, Z0)={(q2,Z0)}
7. δ(q3,b, a)={(q3,a)}
8. δ(q3,c, a)={(q4, )} Shrink the stack by popping matching i=k
9. δ(q4,c, a)={(q4, )} Enter acceptance state if i=k
10. δ(q4, , Z0)={(q5, Z0)}
PUSH DOWN AUTOMATA
Move No. State I/P Symbol Top of the Stack Moves
1 q0 a Z0 (q0,aZ0)
2 q0 a a (q0,aa)
3 q0 b a (q1,ϵ) (q3,a)
4 q1 b a (q1,ϵ)
5 q1 c Z0 (q2,Z0)
6 q2 c Z0 (q2,Z0)
7 q3 b a (q3,a)
8 q3 c a (q4, ϵ)
9 q4 c a (q4,ϵ)
11Z0 is the end
q4 of the stack
ϵ is reached,Z0 So the given language is
(q5,accepted)
accepted.
PUSH Example
DOWN AUTOMATA :
Move State I/P Stack Z0 is the end of
No the stack is
1 q0 abbc Z0 reached, So the
2 q0 bbc aZ0 given language
3 q3 bc aZ0 is accepted.
4 q3 c aZ0
7 q4 Z0
8 q5 Accepted
DISCUSSION
5 MINUTES
When the PFA reject the string ?
QUIZ
Questions from Lecture 30.1 & 30.2
1. A language is accepted by a push down automata if it is:
A) regular B) context free
C) both (a) and (b) D) none of the mentioned
2. The instantaneous PDA is has the following elements
A) State B) Unconsumed input
C) Stack content D) All of the mentioned
QUIZ
Questions from Lecture 30.1 & 30.2
3. The moves in the PDA is technically termed as:
A) Turnstile B) Shifter
C) Router D) None of the mentioned
4. A push down automata can represented using:
A) Transition graph B) Transition table
C) ID D) All of the mentioned
QUIZ
Questions from Lecture 30.1 & 30.2
5. A push down automata is said to be _________ if it has atmost one transition
around all configurations.
A) Finite a) b) c) B) Non regular
d)
C) Non-deterministic D) Deterministic
6. A PDA machine configuration (p, w, y) can be correctly represented as:
A) (current state, unprocessed input, stack B) (unprocessed input, stack content,
content) current state)
C) (current state, stack content,
D) none of the mentioned
unprocessed input)
QUIZ
Questions from Lecture 30.1 & 30.2
7. A DPDA is a PDA in which:
A) No state p has two outgoing B) More than one state can have two or
transitions more outgoing transitions
C) Atleast one state has more than D) None of the mentioned
one transitions
8. If the PDA does not stop on an accepting state and the stack is not empty, the
string is:
A) rejected B) goes into loop forever
C) both (a) and (b) D) none of the mentioned
THANK YOU
