Scribd
Upload
47 views9 pages

Pushdown Automata Overview and Examples

PDA is a type of automaton that recognizes context-free languages by using a stack. A PDA has states, input symbols, stack symbols, transition functions, an initial state, initial stack symbol, and accepting states. The transition function specifies state transitions and stack operations based on the current state, input symbol, and top of stack symbol. For a given CFL, a PDA can be constructed with a transition diagram that grows the stack to represent the generated string and then pops the stack to check for a matching reverse string.

Uploaded by

Saad Ahmed Sazan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
47 views9 pages

Pushdown Automata Overview and Examples

PDA is a type of automaton that recognizes context-free languages by using a stack. A PDA has states, input symbols, stack symbols, transition functions, an initial state, initial stack symbol, and accepting states. The transition function specifies state transitions and stack operations based on the current state, input symbol, and top of stack symbol. For a given CFL, a PDA can be constructed with a transition diagram that grows the stack to represent the generated string and then pops the stack to check for a matching reverse string.

Uploaded by

Saad Ahmed Sazan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Pushdown Automata (PDA)

Reading: Chapter 6

1
PDA - the automata for CFLs
■ What is?
■ FA to Reg Lang, PDA is to CFL
■ PDA == [ ε -NFA + “a stack” ]
■ Why a stack?

Input ε-NFA Accept/reject


string

A stack filled with “stack symbols”


2
Pushdown Automata -
Definition
■ A PDA P := ( Q,∑,Γ, δ,q0,Z0,F ):
■ Q: states of the ε-NFA
■ ∑: input alphabet
■ Γ: stack symbols
■ δ: transition function
■ q 0: start state
■ Z 0: Initial stack top symbol
■ F: Final/accepting states

3
old state input symb. Stack top new state(s) new Stack top(s)

δ: Q x ∑ x Γ => Q x
Γ
δ : The Transition Function
δ(q,a,X) = {(p,Y), …}
1. state transition from q to p
2. a is the next input symbol a X Y
3. X is the current stack top symbol q p
No

Y is the replacement for X;


n

4.
- d

it is in Γ* (a string of stack
e

Y=? Action
te

symbols)
m r

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


i ni

If Y=X: stack top is unchanged


sm

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

4
Example
Let Lwwr = {wwR | w is in (0+1)*}
■ CFG for L : S==> 0S0 | 1S1 | ε
wwr
■ PDA for L :
wwr
■ P := ( Q,∑, Γ, δ,q ,Z ,F )
0 0

= ( {q0, q1, q2},{0,1},{0,1,Z0},δ,q0,Z0,{q2})

5
Initial state of the PDA:

Stack q0

PDA for Lwwr top Z0

1. δ(q0,0, Z0)={(q0,0Z0)}
First symbol push on stack
2. δ(q0,1, Z0)={(q0,1Z0)}

3. δ(q0,0, 0)={(q0,00)}
4. δ(q0,0, 1)={(q0,01)}
5. δ(q0,1, 0)={(q0,10)} Grow the stack by pushing
6. δ(q0,1, 1)={(q0,11)} new symbols on top of old
(w-part)
7. δ(q0, ε, 0)={(q1, 0)}
8. δ(q0, ε, 1)={(q1, 1)} Switch to popping mode, nondeterministically
9. δ(q0, ε, Z0)={(q1, Z0)}
(boundary between w and wR)
10. δ(q1,0, 0)={(q1, ε)}
11. δ(q1,1, 1)={(q1, ε)} Shrink the stack by popping matching
symbols (wR-part)
12. δ(q1, ε, Z0)={(q2, Z0)}
Enter acceptance state
6
PDA as a state diagram
δ(qi,a, X)={(qj,Y)}

Next Current Stack


input stack Top
Current symbol top Replacement
state (w/ string Y)

a, X / Y Next
q q
state
i j

7
PDA for Lwwr: Transition Diagram

Grow stack ∑ = {0, 1}


0, Z0/0Z0 Γ= {Z0, 0, 1}
1, Z0/1Z0 Pop stack for Q = {q0,q1,q2}
0, 0/00
0, 1/01
matching symbols
1, 0/10 0, 0/ ε
1, 1/11 1, 1/ ε

q q q
ε, Z0/Z0
0 ε, Z0/Z0 1 ε, Z0/Z0 2
ε, 0/0
ε, 1/1 Go to acceptance
Switch to
popping mode

This would be a non-deterministic PDA 8


Summary
■ PDAs for CFLs and CFGs
■ Non-deterministic
■ PDA acceptance types
1. By final state
2. By empty stack
■ PDA
■ Transition diagram

You might also like