ì Recognizing CFL

ì PDA – Schematic, Formal Definition

ì PDA – Example with State Diagram

CSC3113: Theory of Computation

ì Understanding the concept of PDA in terms of recognizing non-
regular languages.
ì PDA construction
ì Equivalence of CFG with PDA.

CSC3113: Theory of Computation

 ALL OUTCOME ARE REPRESENTED WITH EXAMPLES

ì Understanding the concept of PDA

ì Relationship among CFL, CFG, PDA, and non-regular languages
ì Able to construct PDAs for given CFL

CSC3113: Theory of Computation

RECOGNIZING CONTEXT FREE LANGUAGES
ì Regular Languages (RL) are recognized by the computational model
Finite Automaton (FA), examples: DFA, NFA.
ì A computational model is required that can recognize some Context
Free Language (CFL).
ì Based on the definition of the language to be recognized, additional
memory with rule of access is required to construct such
computational model.
ì Push Down Automata (PDA) is the computational model that can
recognize some Context Free Language (CFL).
ì PDA contains additional memory with the LIFO (Last In First Out)
access rule. That is, it maintains a stack where an element is pushed
down the stack.
ì Hence the name Push Down Automata.

CSC3113: Theory of Computation

PUSHDOWN AUTOMATA

NON-REGULAR LANGUAGES

ì Have an extra component called stack.

ì Stack provides additional memory beyond the finite amount available in the control.
ì Schematic of a pushdown automaton
ì Control represents the states and transition function
ì The arrow on the tape, containing the input string, represents the input head, pointing at
the next input symbol to be read.
ì The arrow on the stack points the top element.
ì Writing symbol on the stack is referred to as pushing down the symbols.
ì Removing a symbol is referred to as popping up.
ì The top symbol of the stack can be read and removed at any time.

CSC3113: Theory of Computation

FORMAL DEFINITION
ìA pushdown automaton is a 6-touple (Q, Σ, G, d, q0, F), where Q,
Σ, G, and F are all finite sets and
ì Q is the set of states,
ì Σ is the set of alphabet,
ìΣe= Σ È {e}
ì G is the stack alphabet,
ìGe= G È {e}
ì d : Q ´ Σe ´ Ge ® P(Q ´ Ge)
ìDomain of the transition function is the current state, next input symbol
read, and top symbol of the stack.
ìBecause of the nondeterminism, i.e. several legal next moves, d returns
a set of members, each containing the next state and the next stack
symbol.
ì q0ÎQ is the start state, and
ì F Í Q is the set of accept states
CSC3113: Theory of Computation
EXAMPLE: PDA
ì L = {0n1n | n≥0}
ì M = (Q, å, G, d, q1, F), where
ì Q = {q1, q2, q3, q4},
ì å = {0, 1},
ì G = {0, $},
ì Test for an empty stack is done by initially placing a special symbol $ on the stack. If it
ever sees the sign $ again, it knows that the end of stack effectively is empty.
ì F = {q1, q4},
ì d is given in the following table, wherein blank entries signify Æ.
Input: 0 1 e
Stack: 0 $ e 0 $ e 0 $ e
q1 {(q2, $)}
q2 {(q2, 0)} {(q3, e)}
q3 {(q3, e)} {(q4, e)}
q4
CSC3113: Theory of Computation
EXAMPLE - STATE DIAGRAM
ì We write “a, b à c” to signify that when the machine is reading an a
from the input it may replace the symbol b on the top of the stack with a c.
ì State diagram for the PDA M that recognizes {0n1n | n ≥ 0}

Input 0 0 0 1 1 1
0, e à 0
e, e à $
q1 q2
0
0
1, 0 à e
0
1, 0 à e $
q4 q3
e, $ à e Stack
CSC3113: Theory of Computation
TRANSITION TABLE – STATE DIAGRAM
ì d is given in the following table, wherein blank entries signify Æ.

Input: 0 1 e
Stack: 0 $ e 0 $ e 0 $ e
q1 {(q2, $)}
q2 {(q2, 0)} {(q3, e)}
q3 {(q3, e)} {(q4, e)}
q4

e, e à $
q1 q2
0, e à 0

1, 0 à e

1, 0 à e
q4 q3
e, $ à e
CSC3113: Theory of Computation
DETERMINISTIC PDA (DPDA)
ì Just like Finite Automaton (FA), there are Deterministic (DFA in FA) and
Non-Deterministic (NFA in FA) Automaton in PDA.
ì PDAs are inherently nondeterministic (they are not practical
machines).
ì When we say PDA, it represents both deterministic and non-
deterministic PDA that recognizes both deterministic and non-
deterministic CFL respectively.
ì If a PDA is deterministic at each step, that is the next move for every
input has exactly one destination, then the PDA is Deterministic PDA
(DPDA).
ì The previous example was DPDA.
ì The next two examples are for non-deterministic PDAs.

CSC3113: Theory of Computation

EXAMPLE: NON-DETERMINISTIC PDA
ì L = {aibjck | i,j,k≥0 and i=j or i=k}
ì Non-determinism is used here.
ì From state q2, the choice of next Input a a b c c
move is either q3 or q5.
b, a à e c, e à e

e, $ à e
q1 q3 q4
e
à

e, e à $
e
e,

Stack
e, e à e e, e à e e, $ à e
q2 q5 q6 q7

a, e à a b, e à e c, a à e
CSC3113: Theory of Computation
EXAMPLE: NON-DETERMINISTIC PDA

ìL = {wwR | w Î {0,1}*}

e, e à $ 0, e à 0
q1 q2 1, e à 1

e, e à e

0, 0 à e
q4 q3
e, $ à e 1, 1 à e

CSC3113: Theory of Computation

PDA AND CFG
ì A context-free grammar generates a language, a push down
automaton recognizes a language.
ì A Language is generated by a CFG Û It is recognized by a PDA
ì A language L is context-free if and only if there is a pushdown
automata M that recognizes L.
ì Two step proof:
1. Given a CFG G, construct a PDA MG
2. Given a PDA M, make a CFG GM

CSC3113: Theory of Computation

…PDA AND CFG
ì Consider the first example: L = {0n1n | n≥0}
ì CFG: S à 0S1 | ε
ì Generating by deriving the string 000111
ì S à 0S1 à 00S11 à 000S111 à 000111
ì PDA stack: Input String:
Push$
Pop 0$S
1
S, –[Push
Push
pop
Top
As
– Sinput
is
element
0S1
the
εthe
]–top
–has
Pop
start
popelement
been
terminal
the
top
variable
top
scanned
element
terminal
element
1 matches
and
variable
0,
Variable
end
match
with
of
S,current
Match
stack
S,
it with
Match
has
left
input
the
reached
itside
with
first
alphabet
ofinput
left
ruleside
alphabet,
forof
S, rule,
and ifthen
and
matches
then
push
thetoright
go
push the
the side
right
nextof input
side
theofrule,
alphabet.
the push
rule ε.0S1.
As εAsisitempty
is a stack, it will
string notbe pushed
pushed right to left.
here.

$ 1S 1S 0S
1 0S 0 0 0 0 1 1 1

ε, S à ε
Sàε

$S qLOOP ε, $ à
ε, ε à ε
1

ε,

qSTART
à

qACCEPT
εà
S
ε,

ε, ε àS S à 0S1
CSC3113: Theory of Computation
…PDA AND CFG
ì Unambiguous CFG have Deterministic PDA. There is only one way to
generate (by CFG) and recognize (by PDA) each string of the language.
ì Example: S à 0S1 | ε
ì Ambiguous CFG have Non-Deterministic PDA. There is more than one
way to generate (by CFG) and recognize (by PDA) each string of the
language.
ì Example: T à T + T | T x T | (T) | a

CSC3113: Theory of Computation

 PUSHDOWN AUTOMATA
ì Introduction to Theory of Computation, Sipser, (3rd ed),
CFL-2; All Exercises.
ì Elements of the Theory of Computation, Papadimitriou (2nd ed),
CFL-2.

CSC3113: Theory of Computation