PPT: Pushdown Automata (PDA) | Theory of Computation - Computer Science Engineering (CSE) PDF Download

 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
})