PDA
PDA
• Pushdown Automata
• PDA is the Class of Automata associated with CFL
• Finite Automata cannot recognize all context free languages
as FA has strictly finite memory whereas the recognition of a
CFL may require storing an unbounded amount of
information.
PDA
• Eg-
• L={anbn|n>=0}
• When scanning the string, we must check that all a’s are
precede the first b, we also need to count the number of a’s
• Since n is unbounded, this counting cannot be done with a
finite memory.
• We want a machine that can count without limit
PDA
• A pushdown automaton is −
"Finite state machine" + "a stack"
• A pushdown automaton has three components −
1) an input tape,
2) a control unit, and
3) a stack with infinite size.
• The stack head scans the top symbol of the stack.
Deterministic PDA: Formal Definition
• A list of seven elements is called a 7-tuple,
• A PDA can be defined as a 7-tuple
24-05-2022 Ms. Shweta Dhawan Chachra 5
PDA: Formal Definition
PDA is denoted by 7 Tuple: M=(Q, ∑, ᴦ, δ, q0, z, F) where
• Q:Finite set of Internal states of the Control Unit
• ∑:Finite input alphabet
• ᴦ: Finite Set of Stack Symbols/Pushdown symbols
• δ:Q X (∑ U {ε}) X ᴦ ->Q X ᴦ *: Transition function(TF)
or
• δ:Q X ∑ε X ᴦε ->Q X ᴦε *
• q0: Start state of Control Unit, q0 ∈ Q
• z : Stack start Symbol, z ∈ ᴦ, Initially present in the stack
• F: Set of Final States/ Accept State, F ⊆ Q
24-05-2022 Ms. Shweta Dhawan Chachra 6
δ Function
δ Function:-
• δ:Q X (∑ U {ε} X ᴦ ->Q X ᴦ *: Transition function(TF)
or
• δ:Q X ∑ε X ᴦε ->Q X ᴦε *
24-05-2022 Ms. Shweta Dhawan Chachra 7
δ Function:-
δ Function
• δ:Q X (∑ U {ε} X ᴦ ->Q X ᴦ *: Transition function(TF)
or
• δ:Q X ∑ε X ᴦε ->Q X ᴦε *
Domain-
• The Arguments are :-
1) Current State of the control Unit
2) Current Input Symbol
3) Current Symbol on the Top of the stack
Range-
• The Set of pair (q,x) where :-
1) q is Next state of the control Unit
2) x is a string which is put on the top pf the stack , in place of the
single symbol there before
24-05-2022 Ms. Shweta Dhawan Chachra 8
δ Function
δ Function:-
• δ:Q X (∑ U {ε} X ᴦ ->Q X ᴦ *: Transition function(TF)
or
• δ:Q X ∑ε X ᴦε ->Q X ᴦε *
Domain-
• The Arguments are :-
1) Current State of the control Unit
2) Current Input Symbol- Can be ε, indicating a move that does
not consume an input symbol, Also called ε or Null
Transition
3) Current Symbol on the Top of the stack- δ is defined so that
it needs a stack symbol, no move is possible if the stack is
empty
24-05-2022 Ms. Shweta Dhawan Chachra 9
Instantaneous Description
Let M=(Q, ∑, ᴦ, δ, q0, z, F) be a pda
An Instantaneous Description(ID) is (q,x,α)
where q ∈ Q, x ∈ ∑ε , α ∈ ᴦε
1) q is the Current State of the control Unit
2) x is the Unread part of the input string/The part of the
input to be processed
– Say a1,a2,….an
– The PDA will process in a1,a2,….an order only
3) α are the stack contents with the left most symbol
indicating the top pf the stack
• This triplet is called ID
24-05-2022 Ms. Shweta Dhawan Chachra 10
Instantaneous Description
• A move from one ID to another will be denoted by Turnstile
notation
• ⊢ sign is called a “turnstile notation” and represents
one move.
24-05-2022 Ms. Shweta Dhawan Chachra 11
Move Relation-
Let M be a PDA
A move relation between IDs are defined as:-
(q, a1a2………an, z1z2….zn) ⊢ (q’,a2………an,βz2….zn)
if δ(q,a1,z1)=(q’, β)
24-05-2022 Ms. Shweta Dhawan Chachra 12
PDA Example 1
Design a PDA for accepting the language L={anbn|n>=1}
Logic-
PDA Example 1
Design a PDA for accepting the language L={anbn|n>=1}
Rules-
PDA Example 1
Design a PDA for accepting the language L={anbn|n>=1}
Simulation-
PDA Example 2
Design a PDA for accepting the language L={anb2n|n>=1}
Logic-
PDA Example 2
Design a PDA for accepting the language L={anb2n|n>=1}
Rules-
PDA Example 2
Design a PDA for accepting the language L={anb2n|n>=1}
Simulation-
PDA Example 3
Design a PDA for accepting the language L={w | w ∈ (a + b)* and
na(w)=nb(w) }
Logic-
PDA Example 3
Design a PDA for accepting the language L={w | w ∈ (a + b)* and
na(w)=nb(w) }
Transition Rules-
• String “aababb”
PDA Example 3
Design a PDA for accepting the language L={w | w ∈ (a + b)* and
na(w)=nb(w) }
Simulation-
PDA Example 4
Design a PDA for accepting the language L={w | w ∈ (a + b)* and
na(w)>nb(w) }
Logic-
• String “aababab”
PDA Example 4
Design a PDA for accepting the language L={w | w ∈ (a + b)* and
na(w)>nb(w) }
Transition Rules-
PDA Example 4
Design a PDA for accepting the language L={w | w ∈ (a + b)* and
na(w)>nb(w) }
Simulation-
PDA Example 5
Design a PDA for accepting the language L={w | w ∈ (a + b)* and
na(w)<nb(w) }
Logic-
• String “abbab”
PDA Example 5
Design a PDA for accepting the language L={w | w ∈ (a + b)* and
na(w)<nb(w) }
Transition Rules-
PDA Example 5
Design a PDA for accepting the language L={w | w ∈ (a + b)* and
na(w)<nb(w) }
Simulation-
PDA Example 6
Design a PDA that accepts a string of well formed paranthesis.
Consider the paranthesis as (,),{,},[,]
PDA Example 7
Design a PDA for language L={wcwR|w is in (0|1)* and wR is reverse
of w}
Logic-
String 101c101
PDA Example 7
Design a PDA for language L={wcwR|w is in (0|1)* and wR is reverse
of w}
Logic-
• The PDA will go on pushing the symbols onto the stack till it
encounters c in the input
• It reads c but will not push it onto the stack
• For every symbol read after c, it checks whether it matches with
the topmost symbol of the stack
• If input read is 0 ,top=0,pop
• If input read is 1,top=1,pop
• If input ends, we reach zo, replace z0 by null
• Stack empty
• String accepted
PDA Example 7
Design a PDA for language L={wcwR|w is in (0|1)* and wR is reverse
of w}
Transition Rules
Deterministic PDA
Non-Deterministic PDA
NPDA: Formal Definition
NPDA is denoted by 7 Tuple: M=(Q, ∑, ᴦ, δ, q0, z, F) where
• Q:Finite set of Internal states of the Control Unit
• ∑:Finite input alphabet
• ᴦ: Finite Set of Stack Symbols/Pushdown symbols
• δ:Q X (∑ U {ε}) X ᴦ ->2Q X ᴦ *: Transition function(TF)
or
• δ:Q X ∑ε X ᴦε ->2Q X ᴦ *
• q0: Start state of Control Unit, q0 ∈ Q
• z : Stack start Symbol, z ∈ ᴦ, Initially present in the stack
• F: Set of Final States/ Accept State, F ⊆ Q
24-05-2022 Ms. Shweta Dhawan Chachra 35
Non Determinism-Example 1
Design a PDA for language L={wwR|w is non-empty even palindromes
over {a,b} , wR is reverse of w}
Initial a and b read , when top=z0, it will push
Further, If we read a, top=a, Two Moves possible
1) Pop and advance input tape head one position
2) Push the element read and advance input tape head one
position
Further, If we read b, top=b, Two Moves possible
1) Pop and advance input tape head one position
2) Push the element read and advance input tape head one
position
Non Determinism-Example 1
Even length palindromes
String “baab”
String “baaaab”
Non Determinism-Example 1
Design a PDA for language L={wwR|w is non-empty even
palindromes over {a,b} , wR is reverse of w}
δ(q0,a,zo)=(q0,az0)
δ(q0,b,zo)=(q0,bz0)
δ(q0,a,a)={(q0,aa),(q1, ε)}
δ(q0,b,b)={(q0,bb),(q1, ε)}
δ(q1,a,a)=(q1, ε)
δ(q1,b,b)=(q1, ε)
δ(q1,ε,z0)=(q1, ε)
Equivalence of CFG and PDA
24-05-2022 Ms. Shweta Dhawan Chachra 39
CFG to PDA Conversion
For every CFG G, there exists a PDA M accepting L(G) and for
every PDA M, there exists a CFG generating L(M)
24-05-2022 Ms. Shweta Dhawan Chachra 40
CFG to PDA Conversion
Let L be a CFL, There exists a CFG G=(V,T,P,S) generating L
Assume that G is in GNF Form
Thus, G does not contain Epsilon
For each production A->aα of G
Add δ(q,a,A)=(q, α)
For each production A->a of G
Add δ(q,a,A)=(q, ε)
24-05-2022 Ms. Shweta Dhawan Chachra 41
CFG to PDA Conversion-Eg 1
Construct a PDA equivalent to the following grammar:
S->aAA
A->aS|bS|a
24-05-2022 Ms. Shweta Dhawan Chachra 42
CFG to PDA Conversion-Eg 2
Construct a PDA equivalent to the following grammar:
S->aSa|bSb|a
24-05-2022 Ms. Shweta Dhawan Chachra 43
CFG to PDA Conversion-Eg 3
Construct a PDA equivalent to the following grammar:
E->+EE|*EE|id
24-05-2022 Ms. Shweta Dhawan Chachra 44
PDA to CFG Conversion
• Given a PDA accepting a language L, we can obtain a CFG
generating L
PDA to CFG Conversion
• Construct a CFG G=(V,T,P,S) where
• V is a set of objects of the form [q,A,p]
• where p and q are in Q and A is in ᴦ
• If (q,a,A)=(r,BB) then the move tells that if PDA M starts in
state q with A on the top of the stack and gets “a” as next
symbol in the input, then it enters into state r and replaces A
by BB
PDA to CFG Conversion
• The object [q,A,p] derives to a string that allows PDA M to
1) Erase A from the top of the stack,
2) By starting in state q and
3) Ending up in state p using sequence of moves
PDA to CFG Conversion
• To erase A from the top of the stack by starting in state q and
ending in state p, the PDA M has to consume a from input and
enter into the state r
• Then by starting in state r get B erased by entering into any
state say s using sequence of moves followed by getting again
B erased by starting in a state s and ending up in state p
Sequence of moves:-
• Object [q,A,p] derives to a[r,B,s][s,B,p]
• Hence P contains the rules of the form
• [q,a,p]->a[r,B,s][s,B,p]
PDA to CFG Conversion
• Since strings accepted by PDA M are those , that allows PDA
M to erase Z0 from the top of the stack by starting in state q0
and ending up in any state
• The start symbol S will derive to objects [q0,z0,q] for every q
in Q
PDA to CFG Conversion
Give the CFG generating the language accepted by the following
PDA:-
M=({q0,q1},{0,1},{Z0,X}, δ,q0,Z0, ∅) where δ is given below:
1) δ(q0,1,Z0)=(q0,XZ0)
2) δ(q0,1,X)=(q0,XX)
3) δ(q0,0,X)=(q1,X)
4) δ(q0, ε,Z0)=(q0, ε)
5) δ(q1,1,X)=(q1, ε)
6) δ(q1,0,Z0)=(q0,Z0)
PDA to CFG Conversion
M=({q0,q1},{0,1},{Z0,X}, δ,q0,Z0, PDA M to erase Z0 from the top of
∅) where δ is given below: the stack by starting in state q0 and
The productions are ending up in any state
• S->[q0,Z0,q0] The start symbol S will derive to
objects [q0,z0,q] for every q in Q
• S->[q0,Z0,q1]
PDA to CFG Conversion
For Move δ(q0,1,Z0)=(q0,XZ0)
• The productions are The object [q,A,p] derives to a string that
allows PDA M to
1) Erase A from the top of the stack,
2) By starting in state q and
3) Ending up in state p using sequence of
moves
For Move δ(q0,1,X)=(q0,XX)
• The productions are
