Pushdown Automata

Definition
Moves of the PDA
Languages of the PDA
Deterministic PDA’s
1
 Pushdown Automata
 The PDA is an automaton equivalent
to the CFG in language-defining
power.
 Only the nondeterministic PDA
defines all the CFL’s.
 But the deterministic version models
parsers.
 Most programming languages have
deterministic PDA’s.
2
 Intuition: PDA
 Think of an ε-NFA with the
additional power that it can
manipulate a stack.
 Its moves are determined by:
1. The current state (of its “NFA”),
2. The current input symbol (or ε), and
3. The current symbol on top of its
stack.
3
 Intuition: PDA – (2)
 Being nondeterministic, the PDA
can have a choice of next moves.
 In each choice, the PDA can:
1. Change state, and also
2. Replace the top symbol on the stack
by a sequence of zero or more
symbols.
 Zero symbols = “pop.”
 Many symbols = sequence of “pushes.”
4
 PDA Formalism
 A PDA is described by:
1. A finite set of states (Q, typically).
2. An input alphabet (Σ, typically).
3. A stack alphabet (Γ, typically).
4. A transition function (δ, typically).
5. A start state (q0, in Q, typically).
6. A start symbol (Z0, in Γ, typically).
7. A set of final states (F ⊆ Q, typically).
5
 Conventions
 a, b, … are input symbols.
 But sometimes we allow ε as a
possible value.
 …, X, Y, Z are stack symbols.
 …, w, x, y, z are strings of input
symbols.
 , ,… are strings of stack
symbols.
6
 The Transition Function
 Takes three arguments:
1. A state, in Q.
2. An input, which is either a symbol in Σ
or ε.
3. A stack symbol in Γ.
 δ(q, a, Z) is a set of zero or more
actions of the form (p, ).
 p is a state;  is a string of stack
symbols.
7
 Actions of the PDA
 If δ(q, a, Z) contains (p, ) among its
actions, then one thing the PDA can
do in state q, with a at the front of
the input, and Z on top of the stack
is:
1. Change the state to p.
2. Remove a from the front of the input
(but a may be ε).
3. Replace Z on the top of the stack by .
8
 Example: PDA
 Design a PDA to accept {0n1n | n >
1}.
 The states:
 q = start state. We are in state q if we
have seen only 0’s so far.
 p = we’ve seen at least one 1 and may
now proceed only if the inputs are 1’s.
 f = final state; accept.

9
 Example: PDA – (2)
 The stack symbols:
 Z0 = start symbol. Also marks the
bottom of the stack, so we know
when we have counted the same
number of 1’s as 0’s.
 X = marker, used to count the
number of 0’s seen on the input.

10
 Example: PDA – (3)
 The transitions:
 δ(q, 0, Z0) = {(q, XZ0)}.
 δ(q, 0, X) = {(q, XX)}. These two rules
cause one X to be pushed onto the
stack for each 0 read from the input.
 δ(q, 1, X) = {(p, ε)}. When we see a 1,
go to state p and pop one X.
 δ(p, 1, X) = {(p, ε)}. Pop one X per 1.
 δ(p, ε, Z0) = {(f, Z0)}. Accept at bottom.
11
Actions of the Example
PDA
000111

Z0

12
Actions of the Example
PDA
00111

X
Z0

13
Actions of the Example
PDA
0111

X
X
Z0

14
Actions of the Example
PDA
111

X
X
X
Z0
15
Actions of the Example
PDA
11

X
X
Z0

16
Actions of the Example
PDA
1

X
Z0

17
Actions of the Example
PDA

Z0

18
Actions of the Example
PDA

Z0

19
 Instantaneous
Descriptions
 We can formalize the pictures just
seen with an instantaneous
description (ID).
 A ID is a triple (q, w, ), where:
1. q is the current state.
2. w is the remaining input.
3.  is the stack contents, top at the
left.
20
 The “Goes-To” Relation
 To say that ID I can become ID J in
one move of the PDA, we write I⊦J.
 Formally, (q, aw, X)⊦(p, w, ) for
any w and , if δ(q, a, X) contains (p,
).
 Extend ⊦ to ⊦*, meaning “zero or
more moves,” by:
 Basis: I⊦*I.
 Induction: If I⊦*J and J⊦K, then I⊦*K. 21
 Example: Goes-To
 Using the previous example PDA, we
can describe the sequence of moves
by: (q, 000111, Z0)⊦(q, 00111, XZ0)⊦
(q, 0111, XXZ0)⊦(q, 111, XXXZ0)⊦
(p, 11, XXZ0)⊦(p, 1, XZ0)⊦(p, ε, Z0)⊦
(f, ε, Z0)
 Thus, (q, 000111, Z0)⊦*(f, ε, Z0).
 What would happen on input 0001111?
22
 Legal because a PDA can use
Answer ε input even if input remains.

 (q, 0001111, Z0)⊦(q, 001111, XZ0)⊦

(q, 01111, XXZ0)⊦(q, 1111,
XXXZ0)⊦ (p, 111, XXZ0)⊦(p, 11,
XZ0)⊦(p, 1, Z0)⊦ (f, 1, Z0)
 Note the last ID has no move.
 0001111 is not accepted, because
the input is not completely
consumed.
23
 Language of a PDA
 The common way to define the
language of a PDA is by final state.
 If P is a PDA, then L(P) is the set of
strings w such that (q0, w, Z0) ⊦*
(f, ε, ) for final state f and any .
Checklist:
- input exhausted?
- in a final state?

26
 Language of a PDA – (2)
 Another language defined by the
same PDA is by empty stack.
 If P is a PDA, then N(P) is the set of
strings w such that (q0, w, Z0) ⊦*
(q, ε, ε) for any state q.
Checklist:
- input exhausted?
- is the stack empty?

27
 Example: balanced
parenthesis
 PN: ( {q0}, {(,)}, {Z0,Z1}, δN, q0, Z0 )

 δN: δN(q0,(,Z0) = { (q0,Z1Z0) }

 δN(q0,(,Z1) = { (q0, Z1Z1) }


δN(q0,),Z1) = { (q0,) }
δ (q , ,Z ) = { (q , ) }

N 0 0 0

 Accept by empty stack

28
 Example: balanced
parenthesis
 Pf: ( {p0,q0 ,pf}, {(,)}, {X0,Z0,Z1}, δf, p0, X0 ,
pf )

 δf: δf(p0, ,X0) = { (q0,Z0) }

 δf(q0,(,Z0) = { (q0,Z1 Z0) }
 δf(q0,(,Z1) = { (q0, Z1Z1) }
 δf(q0,),Z1) = { (q0, ) }
 δf(q0, ,Z0) = { (q0, ) }
 δf(p0, ,X0) = { (pf, X0 ) }
 Accept by final state 29
 Equivalence of Language
Definitions
1. If L = L(P), then there is another
PDA P’ such that L = N(P’).
2. If L = N(P), then there is another
PDA P’’ such that L = L(P’’).

30
 Deterministic PDA’s
 To be deterministic, there must be at
most one choice of move for any state
q, input symbol a, and stack symbol X.
 In addition, there must not be a choice
between using input ε or real input.
 Formally, δ(q, a, X) and δ(q, ε, X)
cannot both be nonempty.

35
Equivalence of PDA, CFG

Conversion of CFG to PDA

Conversion of PDA to CFG

36
 Overview
 When we talked about closure
properties of regular languages, it
was useful to be able to jump
between RE and DFA
representations.
 Similarly, CFG’s and PDA’s are
both useful to deal with properties
of the CFL’s.
37
 Overview – (2)
 Also, PDA’s, being “algorithmic,” are
often easier to use when arguing that
a language is a CFL.
 Example: It is easy to see how a PDA
can recognize balanced parentheses;
not so easy as a grammar.
 But all depends on knowing that
CFG’s and PDA’s both define the
CFL’s.
38
s same as: “implementing a CFG using a PDA”
Converting a CFG into a
PDA
Main idea: The PDA simulates the leftmost derivation on a
given w, and upon consuming it fully it either arrives at
acceptance (by empty stack) or non-acceptance.
Steps:
1. Push the right hand side of the production onto the
stack, with leftmost symbol at the stack top
2. If stack top is the leftmost variable, then replace it by
all its productions (each possible substitution will
represent a distinct path taken by the non-deterministic
PDA)
3. If stack top has a terminal symbol, and if it matches
with the next symbol in the input string, then pop it
State is inconsequential (only one state is needed)
39
 Formal construction of
PDA from CFG
Note: Initial stack symbol (S)
same as the start variable
in the grammar
 Given: G= (V,T,P,S)
 Output: PN = ({q}, T, V U T, δ, q, S)
 δ:
Before:  For all A  V , add the following After:
A transition(s) in the PDA: 
…

• δ(q,  ,A) = { (q, ) | “A ==>”  P}

…
 For all a  T, add the following
Before:
After:
transition(s) in the PDA: a…
a
• δ(q,a,a)= { (q,  ) } a pop
…

…
40
 Example: CFG to PDA
 G = ( {S,A}, {0,1}, P, S) 1,1 / 
0,0 / 
,A / 01
 P: ,A / A1
,A / 0A1
 S ==> AS |  ,S / 
,S / AS
 A ==> 0A1 | A1 | 01 ,S / S

 PDA = ({q}, {0,1}, {0,1,A,S}, δ, q, S) q

 δ:
 δ(q,  , S) = { (q, AS), (q,  )}
 δ(q,  , A) = { (q,0A1), (q,A1), (q,01) }
 δ(q, 0, 0) = { (q,  ) }
 δ(q, 1, 1) = { (q,  ) }
41
 Simulating string 0011 on
the new PDA … Leftmost deriv.
1,1 / 
0,0 / 
PDA (δ): ,A / 01 S => AS
δ(q,  , S) = { (q, AS), (q,  )}
δ(q,  , A) = { (q,0A1), (q,A1), (q,01) }
,A / A1
,A / 0A1
=> 0A1S
δ(q, 0, 0) = { (q,  ) } ,S /  => 0011S
δ(q, 1, 1) = { (q,  ) } ,S / AS
,S / S => 0011
Stack moves (shows only the successful path): q

0 0
A A 1 1
A 1 1 1 1 1
S S S S S S S S Accept by
empty stack
0 0 1 1 

S =>AS =>0A1S =>0011S => 0011 42

 Converting a PDA into a
CFG
 Main idea: Reverse engineer the
productions from transitions
If δ(q,a,Z) => (p, Y1Y2Y3…Yk):
1. State is changed from q to p;
2. Terminal a is consumed;
3. Stack top symbol Z is popped and replaced with a sequence of
k variables.
 Action: Create a grammar variable
called “[qZp]” which includes the
following production:
– [qZp] => a[pY1q1] [q1Y2q2] [q2Y3q3]… [qk-1Ykqk]

43
 Example: Bracket
matching
 To avoid confusion, we will use b=“(“ and e=“)”
P N: ( {q0}, {b,e}, {Z0,Z1}, δ, q0, Z0 ) 0. S => [q0Z0q0]
1. [q0Z0q0] => b [q0Z1q0] [q0Z0q0]
1. δ(q0,b,Z0) = { (q0,Z1Z0) } 2. [q0Z1q0] => b [q0Z1q0] [q0Z1q0]
2. δ(q0,b,Z1) = { (q0,Z1Z1) } 3. [q0Z1q0] => e

3. δ(q0,e,Z1) = { (q0, )} 4. [q0Z0q0] => 

4. δ(q ,  ,Z ) = { (q ,  ) } Let A=[q0Z0q0]
0 0 0
simplifying,
Let B=[q0Z1q0]

0. S => A
0. S => b B S | 
1. B => b B B | e
1. A => b B A
2. B => b B B
3. B => e
4. A => 
44