Pushdown Automata
Dr Fareeha Anwar
1
Finite Automata
• A finite automaton has a huge limitation.
• It can count only by changing states.
• So an FA can distinguish between at most
|Q| states.
• This limitation bounds the class of languages
that an NFA can recognize to a rather small
category - that of regular languages.
2
The Stack Model
• We add to an NFA an unlimited memory but
we limit the way it is used.
• Our limitation - the memory will be a stack.
• We can read/write only at the top of the stack.
• We still have a finite number of states that can
be used as before.
• we get a machine which is stronger than NFA
but less powerful than TM.
3
Pushdown Automata
• Informally a pushdown automata (PDA) is an
NFA + Stack
state
control
a a b ca a
x
y
z
• To remember or to count we can write to the
stack and can read/pop from it afterwards when
we need the information. 5
Example:
• The following language can be recognized by
PDA but is not regular
L = {anbn | n>0}
• The basic idea of recognition:
– remembering a's by pushing it to the stack.
– comparing the number of b's to the number
of a's by popping one a for each b.
5
Example (cont.)
• If the stack is emptied before the end of input
– the word includes more b's than a's.
• If the stack is not empty at the end of input –
the word includes more a's than b's.
6
Transition function of a PDA
• In NFA a transition function is determined
according to:
1. A current state
2. An input letter
• In PDA we move according to
1. A current state
2. An input letter
3. A letter on top of the stack
• The transition function output is a state and a
letter to be written into the stack. 8
Formal Definition of PDA
• A pushdown automaton is a 6-tuple:
(Q, , , , q0, F)
• Q - is a finite set of states.
• - is the input alphabet.
• - is the stack alphabet.
• : (Q ) → P(Q ) !!!
• q0Q - the start state.
• F Q - a set of accept states. 9
The Transition Function
The transition function (q,,x) = (q',y) reads:
When
– q is the current state
– is the input symbol
– x is the topmost stack symbol
you may
– move to state q’ x y
– push y to the stack z z
,x→y
• The diagram for the PDA is: q q’
10
Possible transition functions
• (q,,x) = (q',y)
– move without reading a symbol from the input
• (q,,) = (q',y)
– move without reading a symbol from the stack
• (q, ,x) = (q',)
– move without pushing a symbol to the stack
• (q, , ) = (q,y)
– push y ,x→y
• (q, , x) = (q,) q q’
– popx
11
Example:
• Change the stack:
(q,,x) = (q',y)
,x→y
q q’
x y
z z
12
Example:
• Popping the stack:
(q,,x) = (q', )
,x→
q q’
x
z z
13
Example:
• Pushing the stack:
(q,,) = (q', y)
,→y
q q’
y
x x
z z
14
Example:
• No change:
(q,,x) = (q', x)
(q,,) = (q', )
,x→x
q q’
,→
x x
z z
15
Example of a PDA
• A state diagram for a PDA that recognizes
{ambn | m=n0}
• The PDA is (Q,,,,q1,F) where
a,→A
• Q={q1,q2,q3,q4} ,→$
• ={a,b} q1 q2
• ={A,$} b,A→
• in the diagram
• q1 the start state q4 q3
,$→
• F={q1,q4} b,A→ 16
Another Example
• A state diagram for a PDA that recognizes
{ambn | n>m 0}
• The PDA is (Q,,,,q1,F) where
a,→A
• Q={q1,q2,q3,q4} ,→$
• ={a,b} q1 q2
• ={A,$} b,$→ b,A→
• in the diagram
• q1 the start state q4 q3
b,$→
• F={q4} b,→ b,A→ 19
Properties of PDA
• With this definition of a PDA there is no explicit
mechanism to test whether the stack is empty.
• We solve the problem by initially placing a
special symbol ($) on the stack.
• The PDA cannot explicitly test for the end of an
input.
• However, the accept state takes effect only
when the machine is at the end of the input.
20
Non Determinism in PDA
• The formal definition of a PDA allows non-
determinism.
• A PDA is called non-deterministic if there
exist at least two possible transitions from a
particular situation (current state q, input
symbol , and stack symbol x).
– Note, that these transitions are not necessarily
defined by (q,,x)
23
Non Determinism in PDA
• A PDA is called deterministic iff it holds the
following three conditions:
– for each qQ, a and x, |(q,a,x)| 1
– for each qQ and x, if (q,,x) then for each
, (q, , x)=
– for each qQ and , if (q,,) then for
each x, (q, ,x)=
Unlike FA deterministic and nondeterministic
PDA are not equivalent in power.
24
Example of Deterministic PDA
• This PDA recognizes {wcwR | w{0,1}* }
,→$ 0,→0
q0 q1 1,→1
c,→
0,0→
q3 q2 1,1→
,$→
25
Example of Nondeterministic PDA
• This PDA recognizes {wwR | w{0,1}* }
• A nondeterminism is a must here.
,→$ 0,→0
q0 q1 1,→1
,→
0,0→
q3 q2 1,1→
,$→
26
The Power of PDA
• What is the power of a PDA? Can it recognize
all context-free languages? Is it stronger?
Theorem: A language is context-free iff
some pushdown automaton recognizes it.
• Proof:
– We show that if L is CFL then a PDA recognizes it.
– We show that is a PDA recognizes L then L is CFL.
