PPT - Pushdown Automata (PDA) Computer Science Engineering (CSE) Notes | EduRev

Theory of Computation

Computer Science Engineering (CSE) : PPT - Pushdown Automata (PDA) Computer Science Engineering (CSE) Notes | EduRev

 Page 1


1
Pushdown Automata (PDA)
Page 2


1
Pushdown Automata (PDA)
2
PDA - the automata for CFLs
n What is?
n FA to Reg Lang, PDA is to CFL
n PDA == [ e -NFA + “a stack” ]
n Why a stack?
e-NFA
A stack filled with “stack symbols”
Input
string
Accept/reject
Page 3


1
Pushdown Automata (PDA)
2
PDA - the automata for CFLs
n What is?
n FA to Reg Lang, PDA is to CFL
n PDA == [ e -NFA + “a stack” ]
n Why a stack?
e-NFA
A stack filled with “stack symbols”
Input
string
Accept/reject
3
Pushdown Automata -
Definition
n A PDA P := ( Q, ?, G, d,q
0
,Z
0
,F ):
n Q: states of the e-NFA
n ?: input alphabet
n G : stack symbols
n d: transition function
n q
0
: start state
n Z
0
: Initial stack top symbol
n F: Final/accepting states
Page 4


1
Pushdown Automata (PDA)
2
PDA - the automata for CFLs
n What is?
n FA to Reg Lang, PDA is to CFL
n PDA == [ e -NFA + “a stack” ]
n Why a stack?
e-NFA
A stack filled with “stack symbols”
Input
string
Accept/reject
3
Pushdown Automata -
Definition
n A PDA P := ( Q, ?, G, d,q
0
,Z
0
,F ):
n Q: states of the e-NFA
n ?: input alphabet
n G : stack symbols
n d: transition function
n q
0
: start state
n Z
0
: Initial stack top symbol
n F: Final/accepting states
d : The Transition Function
d(q,a,X) = {(p,Y), …}
1. state transition from q to p
2. a is the next input symbol
3. X is the current stack top symbol
4. Y is the replacement for X;
it is in G* (a string of stack
symbols)
i. Set Y = e for: Pop(X)
ii. If Y=X: stack top is
unchanged
iii. If Y=Z
1
Z
2
…Z
k
: X is popped
and is replaced by Y in
reverse order (i.e., Z
1
will be
the new stack top)
4
old state Stack top input symb.
new state(s) new Stack top(s)
d : Q x ? x G => Q x G
q
a
X
p
Y
Y = ? Action
i) Y=e Pop(X)
ii) Y=X Pop(X)
Push(X)
iii) Y=Z
1
Z
2
..Z
k
Pop(X)
Push(Z
k
)
Push(Z
k-1
)
…
Push(Z
2
)
Push(Z
1
)
Page 5


1
Pushdown Automata (PDA)
2
PDA - the automata for CFLs
n What is?
n FA to Reg Lang, PDA is to CFL
n PDA == [ e -NFA + “a stack” ]
n Why a stack?
e-NFA
A stack filled with “stack symbols”
Input
string
Accept/reject
3
Pushdown Automata -
Definition
n A PDA P := ( Q, ?, G, d,q
0
,Z
0
,F ):
n Q: states of the e-NFA
n ?: input alphabet
n G : stack symbols
n d: transition function
n q
0
: start state
n Z
0
: Initial stack top symbol
n F: Final/accepting states
d : The Transition Function
d(q,a,X) = {(p,Y), …}
1. state transition from q to p
2. a is the next input symbol
3. X is the current stack top symbol
4. Y is the replacement for X;
it is in G* (a string of stack
symbols)
i. Set Y = e for: Pop(X)
ii. If Y=X: stack top is
unchanged
iii. If Y=Z
1
Z
2
…Z
k
: X is popped
and is replaced by Y in
reverse order (i.e., Z
1
will be
the new stack top)
4
old state Stack top input symb.
new state(s) new Stack top(s)
d : Q x ? x G => Q x G
q
a
X
p
Y
Y = ? Action
i) Y=e Pop(X)
ii) Y=X Pop(X)
Push(X)
iii) Y=Z
1
Z
2
..Z
k
Pop(X)
Push(Z
k
)
Push(Z
k-1
)
…
Push(Z
2
)
Push(Z
1
)
5
Example
Let L
wwr
= {ww
R
| w is in (0+1)*}
n CFG for L
wwr
: S==> 0S0 | 1S1 | e
n PDA for L
wwr
:
n P := ( Q, ?, G, d,q
0
,Z
0
,F)
= ( {q
0
, q
1
, q
2
},{0,1},{0,1,Z
0
}, d,q
0
,Z
0
,{q
2
})
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Dynamic Test

Content Category

Related Searches

practice quizzes

,

ppt

,

pdf

,

Summary

,

study material

,

mock tests for examination

,

shortcuts and tricks

,

PPT - Pushdown Automata (PDA) Computer Science Engineering (CSE) Notes | EduRev

,

video lectures

,

Objective type Questions

,

Extra Questions

,

past year papers

,

Free

,

Previous Year Questions with Solutions

,

Sample Paper

,

PPT - Pushdown Automata (PDA) Computer Science Engineering (CSE) Notes | EduRev

,

Semester Notes

,

PPT - Pushdown Automata (PDA) Computer Science Engineering (CSE) Notes | EduRev

,

Exam

,

Viva Questions

,

Important questions

,

MCQs

;