CSE1008 - Theory of Computation

WIN SEM (2024-25)

Dr. K. Srinivasa Reddy

Professor
SCOPE, VIT-AP University
Module No. 4 Pushdown Automata (PDA) 11 Hours
Definition, Graphical Notation, Instantaneous Descriptions of PDA- Acceptance
by Final state, Acceptance by empty stack, Deterministic PDA - CFG to PDA -
PDA to CFG.
Introduction
Languages and Machines | Chomsky Hierarchy
Introduction
• Automata theory studies abstract machines and the problems they can solve.
• A Pushdown Automaton (PDA) is a type of automaton that uses memory, specifically
a stack. It recognizes context-free languages.
• PDA is more powerful than finite-state machines but less powerful than Turing
machines. It works like a DFA for regular grammars but is designed for context-free
grammars.
• Unlike a DFA, which has limited memory, a PDA can store an unlimited amount of
information using its stack.
• A PDA is an extension of an NFA with ε-transitions, enhanced with a stack for
additional memory.
Introduction
Determine whether L(M) is Regular grammar or not?
Where L(M) = {anbn | 0 ≤ n ≤ k, for some fixed k}
For k=1: L(M) = {ε, ab}
For k=2: L(M) = {ε, ab,aabb}
For k=3: L(M) = {ε, ab, aabb, aaabbb}

q0 a q1 a q2 a q3
b b b b
a/b b b
a/b q7 q6 q5 q4
a a
a
Introduction
• A Finite State Automaton (FSA) is a mathematical model used in computing to
design computer programs and sequential logic circuits.
• It recognizes exactly the regular languages.

Fig. Model of Finite Automata

• The input tape has a limited number of blocks, so it is called “finite”

• The reading head reads one block at a time, moves in one direction, and is
controlled by a finite control unit.
Introduction
L(M) = {anbn | n ≥ 0}, check whether L(M) is Regular grammar or not?
• No
• Need unbounded memory to recognize L(M).
• {anbn | n ≥ 0} requires unbounded counting.
None of the following are regular:
Σ = {0, 1}, L(M) = { 0n12n | n ≥ 0 }
Σ = {a, b, c, …, z}, L(M) = { w | w = wR }
Σ = { (, ) }, L(M) = { Balanced Strings of Parenthesis }

How can we design an automaton with limited states but unlimited memory?
Pushdown automaton (PDA) Model
• Pushdown automaton (PDA) is "Finite state machine" + "a stack"
• PDA has three components
• An input tape, • The stack head scans the top symbol of the stack.
• A control unit, and • A stack does two operations
• A stack with infinite size • Push − a new symbol is added at the top.
• Pop − the top symbol is read and removed.
• A PDA may or may not read an input symbol, but
it must read the top of the stack in every
transition.
• PDA is used as a language acceptor.
• It characterizes the Context Free Languages
(CFL).
Fig. Model of Pushdown Automata • Used to recognize certain types of structured
inputs.
Pushdown automaton (PDA)
A PDA is a non-deterministic machine defined by the seven-tuple
M = (Q, Σ, Г, δ, q0, z0, F) where
Q A finite set of states
Σ A finite input alphabet
Г A finite stack alphabet
q0 The initial / starting state, q0 is in Q
z0 A starting stack symbol, z0 is in Г
F A set of final / accepting states, which is a subset of Q
δ A transition function, (Triple) defines as
δ: Q x (Σ U {ε}) x Г  finite subsets of Q x Г*
• The language of a PDA is the set of strings that the PDA accepts:
L(M) = { w ∈ Σ* | M accepts w }
Example PDA#1
L (M)= { anbn | n ≥ 0} over Σ = { a, b }
IDEA: An infinite pushdown store (stack) solves the problem for {anbn | n ≥ 0} as
follows:
• If ‘a’ is read on the input tape, push it on to stack.
• If character ‘b’ is read on the input tape, pop the corresponding ‘a’ from the stack
(or fail if not matched).
• When input is consumed and if the stack is empty (containing only Z0 or z0) accept
the String otherwise reject it.
Example PDA#1
L (M)= { anbn | n ≥ 0} over Σ = { a, b }
String: aaabbb
Input Stack

a a a b b b Z0

a a a b b b Z0 a

a a a b b b Z0 a a

a a a b b b Z0 a a a
Example PDA#1
L (M)= { anbn | n ≥ 0} over Σ = { a, b }
String: aaabbb
Input Stack

a a a b b b Z0 a a a

a a a b b b Z0 a a

a a a b b b Z0 a

String Accepted
Example PDA#1

String: abbb
Input Stack

a b Z0
b b

Z0 a
a b b b

a b b b Z0

Action not defined, termination

Transition Diagram of PDA
• Nodes represent the states of PDA
• An arrow labeled "start" shows the initial state.
• Double-circled states indicate the final states.
• Arcs correspond to transitions are labeled a, b / Z from state q to state p
• A transition of the form a, b / Z means “If the Current symbol is ‘a’ and current stack
symbol is ‘b’ then pop ‘b’ and push the string Z.
• If a transition read the top symbol of stack, it always pop that symbol and it replaces the
existing symbol, with a symbol newly pushed on to the stack.
PDA M = ({q1, q2, q3}, {a, b}, {a, Z0}, δ, q1, Z0, {q3})
where δ:
1. δ(q1, a, Z0 ) = {(q1, aZ0)} // Push Z0 first, then a on to stack
a, Z0 → aZ0 (1) 2. δ(q1, a, a) = {(q1, aa)}
a, a → aa (1) b, a → ε (2) 3. δ(q1, b, a) = {(q2, ε)}
4. δ(q1, ε, Z0) = {(q3, ε)} // Null string acceptance
b, a → ε (2) ε, Z0 → ε (3)
q1 q2 q3 5. δ(q2, b, a) = {(q2, ε)}
6. δ(q2, ε, Z0) = {(q3, ε)} // End of the string acceptance
ε, Z0 → ε (3)
7. δ(q1, b, Z0) = Ø // illegal, string begins with ‘b’ rejected
Exercise: Design PDA for 8. δ(q2, a, a) = δ(q2, a, Z0) = δ(q2, b, a) δ(q2, b, Z0) =Ø /
L= { ancbn | n ≥ 0} over Σ = { a, b, c} illegal, string rejected
Transitions in PDA
Example:
a , eb  cdf
q1 q2
input

 a 
 
 a 

stack stack
e top
top c push
pop d String in
string b reverse
f
h Replace
e h
$
e
$
Transition Diagram of PDA
a , eb  cdf
q1 q2
Equivalent
transitions
pop
a, e   a, b  
q1
,    push
a,   f a,   d a,   c q2
PDA#2: PDA for Palindromes
Design PDA for L = {w|w#wR , w ɛ {a,b}*} [w#wreverse]
• A palindrome is a string that is the same forwards and backwards.
• Example: {a#a, bba#abb,ab#ba}
• How to build a PDA for palindrome of Odd length?

IDEA:
• Length of any string w ∈ L is odd, w must have a symbol ‘#’ exactly in the middle
position;
• i.e., |w| = 2n+1 for some n ≥ 0, and the (n+1)th symbol in w is the middle one.
• If a string w of length 2n + 1 satisfies w = wR, the first n symbols must match (in
reverse order) the last n symbols, and the middle symbol doesn’t have to match
anything.
• Here, do comparison not counting.
PDA#2: PDA for Palindromes
• Place input head upon leftmost input symbol on tape.
• while symbol being scanned ≠ #
if symbol scanned = ‘a’, put a on stack
if symbol scanned = ‘b’, put b on stack
Advance input head to next symbol
• Advance input head past #
• Repeat
if (symbol scanned = ‘a’ and stack[top] = ‘a’)
or (symbol scanned = ‘b’ and stack[top] = ‘b’)
then remove top disk;
advance input head until (Stack is empty) or (no input remains) or
(no element is removed).
• If input has been read and Stack is empty, then accept
PDA#2: PDA for Palindromes
w = ab#ba

Input a b # b a

b b b
Stack a a a a a

Push Push Neither Pop b Pop a

Push nor POP

• At the right end of the input, the machine reads the ‘a’ and removes the ‘a’ from
the stack.
• The stack is empty, accepts the string.
PDA#2: PDA for Palindromes
w = ab#b

Input a b # b

b b b
Stack a a a a a

Push Push Neither Pop b Input

Push nor POP exhausted

• Here, Input is exhausted, but stack contains the ‘a’.

• Hence, reject the string.
Transition Diagram of PDA
PDA for L (M)= { w | w#wR | w ε {a, b}*
a, a → ε (10)
a, Z0 → aZ0 (1) b, b → ε (11)
a, a → aa (2) ε, Z0 → ε (12)
a, b → ab (3)

q1 #, Z0 →Z0 (7) q2
#, a → a (8)
b, Z0 → bZ0 (4) #, b → b (9) #, Z0 →Z0 (13)
b, b → bb (5) #, a → a (14)
b, a → ba (6) #, b → b (15)
q3
What about the string ab##ba? #, Z0 →Z0 (16)
[Two or more # symbols] Reject #, a → a (17)
#, b → b (18)
PDA#2: PDA for Palindromes
M = ({q1, q2, q3}, {a, b, #}, {Z0, a, b}, δ, q1, Z0, {q2})
δ:
(1) δ(q1, a, Z0) = {(q1, aZ0)} (4) δ(q1, b, Z0)={(q1, bZ0)}
(2) δ(q1, a, a) = {(q1, aa)} (5) δ(q1, b, b) = {(q1, bb)}
(3) δ(q1, a, b) = {(q1, ab)} (6) δ(q1, b, a) = {(q1, ba)}
(7) δ(q1, #, Z0) = {(q2, Z0)}
(8) δ(q1, #, a) = {(q2, a)} (9) δ(q1, #, b) = {(q2, b)}
(10) δ(q2, a, a) = {(q2, ε)} (11) δ(q2, b, b) = {(q2, ε)}
(12) δ(q2, ε, Z0) = {(q2, ε)}

(12) δ(q2, #, Z0) = {(q3, Z0)} (16) δ(q3, #, Z0) = {(q3, Z0)}
(13) δ(q2, #, a) = {(q3, a)} (17) δ(q3, #, a) = {(q3, a)}
(14) δ(q2, #, b) = {(q3, b)} (18) δ(q3, #, b) = {(q3, b)}
PDA#3:
Language of balanced parenthesis:
Example: (())() ()()
IDEA
– On seeing a ( push “(” on to the stack
– On seeing a ) pop “(” from the stack
– If attempt to pop an empty stack, reject
– If stack not empty at the end, reject
– Else accept
M = ({q1}, {(, )}, {(, Z0}, δ, q1, Z0, Ø) where δ:
1. δ(q1, (, Z0) = {(q1, (Z0)} // L-on top-then- # lower
2. δ(q1, (, () = {(q1, (()}
3. δ(q1, ), () = {(q1, ε)}
4. δ(q1, ε, Z0) = {(q1, ε)} //if ε read & stack hits bottom, accept
5. δ(q1, ), Z0) = Ø // illegal, string rejected
6. δ(q1, ε, L) = Ø // illegal, string rejected
PDA#3:
Transition Diagram: M = ({q1}, {(, )}, {(, Z0}, δ, q1, Z0, Ø)

(, Z0 | (Z0 No Final State

ε, Z0 |ε q1 (, ( | ((

String:(()) ), ( | ε
Current Input Stack Transition
(()) Z0 initial status
()) (Z0 (1) Push (
)) ((Z0 (2) Push (
) (Z0 (3) Pop L
ɛ Z0 (3) Pop L
- - (4) Pop Z0
PDA#4: L(M)= {aibjck|i,j,k ≥ 0, i = j or j = k }
Case 1:
• If the string is ai bj ck with i = j, then match for a’s and b’s irrespective of numbe
of c’s.
• i=j=1, k=0 ab
• i=j=2 k=1 aabbc
• i=j=3 k= 8 aaabbbcccccccc

a, Z0 → aZ0 Ignore any

Match for number of trailing c’s
a’s and b’s a, a → aa
c, Z0 → Z0
b, a → ε
c, Z0 → Z0
q1 q2
ɛ, Z0 → ɛ
PDA for L (M)= {anbnck | i=j=n}
PDA#4: L(M)= {aibjck|i,j,k ≥ 0, and i = j or j = k }
Case 2:
• If the string is ai bj ck with j = k, then match for b’s and c’s irrespective of
number of a’s.
• i=0 j=k=1 bc
• i=1 j=k=1 abbcc
• i=2 j=k=3 aabbbccc
Ignore any b, b → bb Match of b’s and c’s
number of a, Z0 → Z0 c, b → ε
leading a’s
b, Z0 → bZ0 ε, Z0 → ε q5
q3 q4

PDA for L (M)= {aibncn | j=k=n}

PDA#4: L(M)= {aibjck|i,j,k ≥ 0, and i = j or j = k }
a, Z0 → aZ0 PDA for L (M)= {anbnck | i=j=n}
a, a → aa
Merging of c, Z0 → Z0
b, a → ε
Case-1 & Case-2
c, Z0 → Z0
X q1 q2
q0 ε, Z0→Z0 Case-1 ε, Z0 → ε

Case-2 b, b → bb
ε, Z0→ Z0 a, Z0 → Z0 c, b → ε
b, Z0 → bZ0 ε, Z0 → ε q5
X q3 q4
Remove initial states of PDA for L (M)= {aibncn | j=k=n}
Case-1 & Case-2
M = ({q0, q1, q2, q3, q4, q5}, {a,b,c}, {a,b,Z0}, δ, q0, Z0, {q2, q5})
PDA#5: L(M)= {aibjck|i,j,k ≥ 0, and i+j=k }
Example Strings:
ac bc abcc aabccc
IDEA:
• For every ‘a’ and ‘b’ read, push an ‘x’ onto the stack.
• For every ‘c’ pop ‘x’ from the stack.

Pushing a and b
on to stack
c, x → ɛ
a, Z0 → xZ0
ɛ, Z0 → ɛ
a, x → xx b, x → xx

q1 b, Z0 → xZ0 c, x → ɛ q3
q2

M = ({q1, q2, q3}, {a,b}, {x,Z0}, δ, q1, Z0, φ)

PDA#6: L(M)= { a2nb3n | n ≥ 0}
Example: n=0 n=1 n=2
ɛ aabbb aaaabbbbbb
IDEA:
• Push ‘x’ onto the stack for every 2 a’s read. M = ({q1, q2, q3, q4, q5, q6}, {a,b}, {x,Z0}, δ, q1, Z0, {q6})
• Pop ‘x’ from the stack for every 3 b’s read.

number of a’s q2
multiple of 2 ɛ, Z0 → ɛ q6
a, Z0 → Z0 a, Z0 → xZ0
a, x → xx
a, x → x b, x → x
q1 ɛ, x → x q4
ɛ, Z0 → ɛ number of b’s
multiple of 3
b, Z0 → Z0 b, x → ɛ
b, x → x
q3 q5
PDA#7: Equal number of 'a's and 'b's

Example: ab, abab, abbbaa, ba, bbaa

a,$  a$ b,$  b$
a,a  aa b,b  bb
a,b   b,a  

q1 , $  $ q2
M = ({q1, q2}, {a,b}, {a,b,Z0}, δ, q1, $, {q2})
PDA#8: PDA for no. of 'a’s > [Link] 'b‘s

Example: a,aab, aaaabbb

a, Z0 → aZ0
Matching for a, a → aa
ε, Z0 → ε
a’s and b’s a, b → ε
ε, a → ε q2
q1
Checking for
more a’s than b’s
b, Z0 → bZ0
b, b → bb
b, a → ε
M = ({q1, q2}, {a,b}, {a,b,Z0}, δ, q1, Z0, {q2})
PDA#9: PDA for no. of 'a’s < [Link] 'b‘s
Example: b, abb, aabbb
a, Z0 → aZ0
a, a → aa
Matching for a, b → ε ε, Z0 → ε
a’s and b’s
q1 ε, b → ε q2
b, Z0 → bZ0 Checking for
b, b → bb more b’s than a’s
b, a → ε

M = ({q1, q2}, {a,b}, {a,b,Z0}, δ, q1, Z0, {q2})

PDA#10: PDA accepting {anbman | m,n >=1}
Example: n m String
1 1 aba
2 3 aabbbaa
IDEA:
• Push ‘a’ onto the stack.
• Skip all ‘b’s.
• Pop all ‘a’s for matching
Matching for a’s
Pushing a’s onto stack
a, Z0 → aZ0 Skipping b’s ɛ, Z0 → ɛ
a, a → aa b, a → a a, a → ɛ

b, a → a q1 a, a → ɛ
q0 q2
M = ({q0, q1, q2}, {a,b}, {a,Z0}, δ, q1, Z0, φ)
PDA#11: PDA for Arithmetic
ARITH = {w ∈ Σ* | w is a legal arithmetic expression, where Σ = { int, +, *, (, ) } }
Example Strings:
• int + int * int
• ((int + int) * (int + int)) + (int)
• Can we build a PDA for ARITH?

Checking for Popping ‘)’

Pushing ‘(’s onto stack expressions

q1 q2 q3

M = ({q1, q2 , q3}, {int, +, *, (, ) }, {(, Z0}, δ, q1, Z0, {q3})

Non-Determinism
PDAs are non-deterministic: Allows non-deterministic transitions

q2
a, b  c

q1 q1 , b  c q
2

a, b  c q
  transition
3
Non-Deterministic PDA
a, ɛ → a
b, ɛ → b • The transition does not pop anything from the stack.
• It just pushes on a new symbol instead.

Σ, ɛ → Σ • The Σ here refers to the same symbol in both contexts.

• It is a shorthand for “treat any symbol in Σ this way”
Example PDA#4:

• This transition means “don't consume any input, don't change the top of the
stack, and don‘t add anything to a stack”.
• It's the equivalent of an ε-transition in NFA.
PDA#12: L {x | x = wwr and w in {0,1}*}
Note: length |x| is even
IDEA
• Push the symbols read onto the stack.
• At each point non-deterministically guess, that middle of the string has been
reached or if the next symbol read is the middle of the string and will not be
put on the stack.
• Pop off the symbols from the stack if they match the input symbols read.
• If the symbols popped are the same symbols that were pushed on earlier and
the stack empties as the input is finished, then accept. Otherwise, reject.
PDA#12: L {x | x = wwr and w in {0,1}*}

• This transition indicates lets us consume one character before start matching
what was just saw.
• This idea is useful to match Even-length palindromes
PDA#12: L {x | x = wwr and w in {0,1}*}
0, Z0 / 0 Z0
1, Z0 / 1 Z0
0, 0 / 0 0
0, 1 / 0 1
1, 0 / 1 0 0, 0 / ε
1, 1 / 1 1 1, 1 / ε

Start
q0 q1 q2
ε, Z0 / Z0 ε, Z0 / Z0
ε, 0 / 0
ε, 1 / 1
PDA#12: L {x | x = wwr and w in {0,1}*}
(q0, 1111, Z0)
ε WRONG GUESS
1 ε
(q0, 111, 1Z0) (q1, 1111, Z0) (q2, 1111, Z0)
1
ε
1
(q0, 11, 11Z0) (q1, 111, 1Z0) (q1, 11, Z0)
1
ε WRONG GUESS 1
(q0, 1, 111Z0) (q1, 11, 11Z0) 1 (q2, 11, Z0)
1
ε
(q0, ε, 1111Z0) (q1, 1, 111Z0) (q1, 1, 1Z0)
1
1 1
(q1, ε, 1111Z0) (q1, ε, 11Z0) (q1, ε, Z0)
WRONG GUESS ε
WRONG GUESS CORRECT GUESS (q2, ε, Z0)
PDA
PDA#1: L (M)= { anbn | n ≥ 0}
PDA#2: L(M) = {w|w#wR , w ɛ {a,b}*}
PDA#3: L(M) = {w| Matching of Parenthesis, w ɛ {(,)}*}
PDA#4: L(M) = {aibjck|i,j,k ≥ 0, and i = j or j = k }
PDA#5: L(M) = {aibjck|i,j,k ≥ 0, and i +j = k }
PDA#6: L(M) = {a2nb3n|n ≥ 0}
PDA#7: L(M) = {w|w has equal number of a’s and b’s}
PDA#8: L(M) = {w|w has a greater number of a’s than b’s}
PDA#9: L(M) = {w|w has a greater number of b’s than a’s}
PDA#10: L(M) = {anbman|n,m ≥ 1}
PDA#11: L(M) = {w ∈ Σ* | w is a legal arithmetic expression,
where Σ = { int, +, *, (, ) }
PDA#12: L(M) = {x | x = wwR , w ɛ {0,1}*}
Instantaneous Description (ID)
• M = (Q, Σ, Г, δ, q0, z0, F) be a PDA, and configuration of PDA at any given
instance is an instantaneous description (ID) is a triple (q, w, γ), where q is in
Q, w is in Σ* and γ is in Г*.
• q is the current state
• w is the unused input
• γ is the current stack contents

• Notation: Turnstile (Ⱶ) [Read as Fallen T]

• Ⱶ sign represents one move
• Ⱶ * sign represents a sequence of moves
Instantaneous Description (ID)
• Let a be in Σ U {ε},
w be in Σ*,
z be in Г,
and α and β both be in Г*. Then:
(q, aw, zα) Ⱶ (p, w, βα)
if δ(q, a, z) contains (p, β).

• Intuitively, if I and J are instantaneous descriptions, then I Ⱶ J means that J

follows from I by one transition.
Instantaneous Description (ID)
Example:
(q1, (())), (#) Ⱶ (q1, ())),((#)
• Ⱶ * is the reflexive and transitive closure of Ⱶ.
• I Ⱶ * K for each instantaneous description
If I Ⱶ J and J Ⱶ * K then I Ⱶ * K
• If I and J are instantaneous descriptions, then I Ⱶ* J means that J follows from
I by zero or more transitions.
Acceptance by PDA
A PDA can accept a language using two different acceptance criteria:
1. Acceptance by Final State
• A PDA accepts a string if, after reading the entire input, it is in an accepting (final) state.
• The stack may or may not be empty at the end.
• This method is similar to how a Finite Automaton works, except the PDA has a stack for
additional memory.
2. Acceptance by Empty Stack
• A PDA accepts a string if, after reading the entire input, the stack is empty.
• The final state is not considered in this method.
• It ensures that all symbols pushed onto the stack are eventually popped, maintaining
balance in cases like parentheses checking or palindrome detection.
Equivalence of Both Acceptance Methods
• Both acceptance methods are equivalent in terms of computational power.
• Any language accepted by a Final State PDA can also be accepted by an Empty Stack PDA,
and vice versa.
• However, the construction of one from the other may require modifications in transitions and
additional states.
Acceptance by PDA
M = ({q1, q2, q3}, {a, b}, {a, Z0}, δ, q1, Z0, {q3}
a, Z0 → aZ0 (1)
a, a → aa (1) b, a → ε (2) PDA acceptance by Final State
b, a → ε (2) ε, Z0 → ε (3)
q1 q2 q3

ε, Z0 → ε (3)

PDA for L (M)= { anbn | n ≥ 0}

M = ({q1}, {(, )}, {(, Z0}, δ, q1, Z0, Ø)

(, Z0 | (Z0
PDA acceptance Empty Stack
ε, Z0 |ε q1 (, ( | (( No Final State
), ( | ε
PDA for L (M)= {Matching of Parenthesis}
PDA acceptance
• By Empty Stack: Let M = (Q, Σ, Г, δ, q0, Z0, F) be a PDA, then the language accepted by empty
stack, denoted LE(M), is the set = {w | (q0, w, Z0) Ⱶ* (p, ε, ε) for some p in Q}
Checklist:
– Is Input exhausted?
– Is the stack empty?
• By Final State : Let M = (Q, Σ, Г, δ, q0, z0, F) be a PDA, then the language accepted by final state,
denoted LF(M), is the set = {w | (q0, w, Z0) Ⱶ* (p, ε, γ) for some p in F and γ in Г*}
Checklist:
– Is Input exhausted?
– Is the state being final state?
– Contents in stack are irrelevant.
• Empty stack and final state: Let M = (Q, Σ, Г, δ, q0, Z0, F) be a PDA, then the language accepted by
empty stack and final state, denoted L(M), is the set = {w | (q0, w, Z0) Ⱶ * (p, ε, ε) for some p in F}
Checklist:
– Is input exhausted?
– Is the state being final state?
– Is the stack empty?
EQUIVALENCE OF ACCEPTANCE BY FINAL STATE AND EMPTY STACK

Language L has a PDA that accepts it by final state if and only if L has a PDA that
accepts it by empty stack

• Let PE be a PDA by Empty stack.

• Let PF be a PDA by Final state.
• A language is generated by a CFG iff it is accepted by a PDA by empty stack
iff it is accepted by a PDA by final state
PDA CONVERSION: EMPTY STACK TO FINAL STATE
If L = N(PE) for some PDA PE = (Q, Σ, Γ, δN, q0, Z0, φ) then there is a PDA PF such that L = L(PF)

PE

Fig. PDA for PE

Empty Stack Mechanism:
• Input is exhausted and stack is empty.
PDA CONVERSION: EMPTY STACK TO FINAL STATE
• Converting PE to PF (Accept by Final State)
• Final State Mechanism:
– Input is exhausted. • Idea
– State being the final state. – Use a new symbol X0 as bottom of stack for PF
– Stack contents are irrelevant.

PE

Fig. PDA for PE

How to Modify? How to keep X0

Here no final states. as bottom of
Stack?
PDA CONVERSION: EMPTY STACK TO FINAL STATE
• Idea
– Introduce new states p0 and pf
– p0 to put symbol X0 as bottom of Stack, not part of ℾ.

ε, Z0 → Z0X0
Z0
X0
Initial Stack
Figure: PF simulates PE and accepts if PE empties the stack
Stack Contents
X0 serves two purposes: by the time
• It is the start symbol of the stack. PE completed
• It acts as a marker to detect when the stack is empty in PE. X0 Empty Stack
Detecting an Empty Stack:
• When PF sees X0 at the top of stack, then it knows that PE would empty its stack on the same input.
Introducing a New Accepting State pf
PDA CONVERSION: EMPTY STACK TO FINAL STATE
The specification of PF is as follows:
PF = (QU{p0, pf}, Σ, Γ U {X0}, δF, p0, X0, {pf})
where δF is defined by:
a) δF(p0, ε, Z0) = {(q0, Z0X0)}. In its start state, PF makes a spontaneous transition to the start
state of PE, pushing its start symbol X0 onto the stack.
b) For all states q in Q, inputs a in Σ or a = ε, and stack symbols Y in Γ, δF(q, a, Y) contains all
the pairs in δE(q, a, Y).
c) In addition to rule (b), δF(q, ε, X0) contains (pf, ε) for every state q in Q.
PDA CONVERSION: EMPTY STACK TO FINAL STATE

(, Z0|(Z0
(, (|((
(, Z0|(Z0 ), (|ε
ε, Z0|ε (, (|(( ε, Z0|ε
q0
p0 q0 pf
), (|ε ε, Z0|Z0X0 ε, X0|ε
PDA for matching of PDA for matching of
Parenthesis by Empty Stack Parenthesis by Final State
PDA CONVERSION: FINAL STATE TO EMPTY STACK
Idea:
• Converting PF to PE (Accept by Empty Stack)
• Empty Stack Mechanism:
– Input is exhausted.
– Stack is empty

ε, Z0 → Z0X0

Fig. PDA for PF

Figure : PE simulates PF and empties its stack when and
only when PE enters an accepting state
PDA CONVERSION: FINAL STATE TO EMPTY STACK
Theorem:
• Let L be L(PF) for some PDA PF = (Q, Σ, Γ, δF, q0, Z0, F).
– there is a PDA PE such that L = N(PE)
Proof:
• Let PE = (QU{p0, p}, Σ, ΓU{X0}, δE, p0, X0, φ), Where δE is defined by:
a) δE(p0, ε, X0) = {(q0, Z0X0)}. We start by pushing the start symbol of PF on to the stack and
going to the start state of PF.
b) For all states q in Q, input symbols a in Σ or a = ε, and Y in Γ, δE(q, a, Y) contains every pair
that is in δF(q, a, Y). That is, PE simulates PF.
c) For all accepting states q in F and stack symbols Y in Γ or Y = X0, δE(q, ε, Y) contains (p, ε).
By this rule, whenever PF accepts, PE can start emptying its stack without consuming any
more input.
d) For all stack symbols Y in Γ or Y = X0, δE(p, ε, Y) = {(p, ε)}. Once in state p, which only
occurs when PF has accepted, PE pops every symbol on its stack, until the stack is empty. No
further input is consumed.
PDA#6: L(M)= { a2nb3n | n ≥ 0}
Example: n=0 n=1 n=2
ɛ aabbb aaaabbbbbb
IDEA:
• Push ‘x’ onto the stack for every 2 a’s read.
• Pop ‘x’ from the stack for every 3 b’s read.
M = ({q1, q2, q3, q4, q5, q6}, {a,b}, {x,Z0}, δ, q1, Z0, {q6})
number of a’s q2
multiple of 2 ɛ, Z0 → ɛ q6
a, Z0 → Z0 a, Z0 → xZ0
a, x → xx
a, x → x b, x → x
q1 ɛ, x → x q4
ɛ, Z0 → ɛ number of b’s
multiple of 3
b, Z0 → Z0 b, x → ɛ
b, x → x
q3 q5
PDA: L(M)= { a2nb3n | n ≥ 0}
Example: n=0 n=1 n=2
ɛ aabbb aaaabbbbbb
IDEA:
• Push ‘x’ onto the stack for every 2 a’s read.
• Pop ‘x’ from the stack for every 3 b’s read.
M = ({q1, q2, q3, q4, q5} U {q0,p}, {a,b}, {x,Z0,X0}, δE, q0, X0, φ)

number of a’s q2
multiple of 2 ɛ, Z0 → ɛ q6
a, Z0 → Z0 a, Z0 → xZ0
a, x → xx ɛ, X0 → ɛ
a, x → x b, x → x
q1 ɛ, x → x q4 p
ɛ, Z0 → ɛ number of b’s
multiple of 3
q0 b, Z0 → Z0 b, x → ɛ
b, x → x
q3 q5
EQUIVALENCE OF PDA AND CFG

• The languages defined by PDA’s are exactly the context-free languages.

Fig: Organization of constructions showing equivalence

of three ways of defining the CFL’s
EQUIVALENCE OF PDA AND CFG
Given a CFG, G = (V, T, P, S), construct the PDA M that accepts L(G) by empty
stack as follows:
M = ({q}, T, V ∪ T, δ, q, S, φ)
δ is defined by:
1. For all A ε V, add the following transition(s) in the PDA,
δ(q, ε, A) = {(q, β) | A → β is a production of P}.
2. For each terminal a in T, δ(q, a, a) = {(q, ε)}.
EQUIVALENCE OF PDA AND CFG
Example-1:
Consider the CFG G = (V, T, P, S) with V = {S}, T = {a, b}, and
P = {S → aSb, S → ab} which generates the language L = {anbn| n≥1} and
process the string aabb.
Solution for PDA:
1. For Non-Terminal symbol V= {S}
δ(q, ε, S) = {(q, aSb), (q, ab)}
2. For Terminal symbols T = {a, b}
δ(q, a, a) = (q, ε)
δ(q, b, b) = (q, ε)
EQUIVALENCE OF PDA AND CFG
Example: aabb
• Assume S is already in Stack, and it is top of stack
• S can be inserted in to stack by adding a rule
δ(q0, ε , ε)  (q,S)
• δ(q, ε, S) = {(q, aSb), (q, ab)}
S
• δ(q, aabb, S) Undefined transition. Stack
• Consider as δ(q, εaabb, S) =(q, aSb)
δ(q, ε, S) = {(q, aSb), (q, ab)} [1st Choice chosen] a
• Pop S, push aSb into stack. Advance input. S
b
Use the non-determinism of the PDA to match terminal
symbols on the stack with symbols in the input string before the Stack
first variable.
EQUIVALENCE OF PDA AND CFG
a • δ(q, aabb, aSb) = (q, ε) [Since δ(q, a, a) = (q, ε)]
S • Input is ‘a’ and top of stack is ‘a’, matching, advance input
b and pop stack.
Stack
• δ(q, abb, Sb) [No rule]
S • Consider this as δ(q, εabb, Sb) = (q, ab), Pop S, push ab into
stack.
b
• (q, ε, S) = {(q, aSb), (q, ab)} [2nd Choice Chosen]
Stack
a
b
b
Stack
EQUIVALENCE OF PDA AND CFG

a • δ(q, abb, abb) = (q, ε)

b • Input is ‘a’ and top of stack is ‘a’, matching, advance input
and pop stack.
b
Stack
δ(q, bb, bb) = (q, ε)
b
b
Stack
b
Stack Empty
Stack
δ(q, b, b) = (q, ε)
EQUIVALENCE OF PDA AND CFG
Example-2: Example-3:
Given CFG G: Given CFG G:
SAS| ε SaAA
A0A1|A1|01 AaS|bS|a
Solution for PDA: Solution for PDA:
1. For Non-terminals 1. For Non-terminals
δ (q, ε, S) = {(q, AS), (q, ε)} δ (q, ε, S) = {(q, aAA)}
δ (q, ε, A) = {(q, 0A1), (q, A1), (q, 01)} δ (q, ε, A) = {(q, aS), (q, bS), (q, a)}
2. For Terminals 2. For Terminals
δ (q, 0, 0) = {(q, ε)} δ (q, a, a) = {(q, ε)}
δ (q, 1, 1) = {(q, ε)} δ (q, b, b) = {(q, ε)}
EQUIVALENCE OF PDA AND CFG
S → 0BB
B → 0S | 1S | 0
Solution:
The PDA can be given as:
A = {(q), (0, 1), (S, B, 0, 1), δ, q, S, Φ }
The production rule δ can be:
R1: δ(q, ε, S) = {(q, 0BB)}
R2: δ(q, ε, B) = {(q, 0S) | (q, 1S) | (q, 0)} δ(q, 010000, S) ⊢ δ(q, 010000, 0BB)
R3: δ(q, 0, 0) = {(q, ε)} ⊢ δ(q, 10000, BB) R1
R4: δ(q, 1, 1) = {(q, ε)} ⊢ δ(q, 10000,1SB) R3
Test the string 010000 against PDA: ⊢ δ(q, 0000, SB) R2
⊢ δ(q, 0000, 0BBB) R1
⊢ δ(q, 000, BBB) R3
⊢ δ(q, 000, 0BB) R2
⊢ δ(q, 00, BB) R3
⊢ δ(q, 00, 0B) R2
⊢ δ(q, 0, B) R3
EQUIVALENCE OF PDA AND CFG
S → aSb
S→a|b|ε
The PDA can be given as:
P = {(q), (a, b), (S, a, b, z0), δ, q, z0, Φ }
The mapping function δ will be:
R1: δ(q, ε, S) = {(q, aSb)}
R2: δ(q, ε, S) = {(q, a) | (q, b) | (q, ε)}
R3: δ(q, a, a) = {(q, ε)} δ(q, εaaabb, S) ⊢ δ(q, aaabb, aSb) R3
R4: δ(q, b, b) = {(q, ε)} ⊢ δ(q, εaabb, Sb) R1
R5: δ(q, ε, z0) = {(q, ε)} ⊢ δ(q, aabb, aSbb) R3
String: aaabb ⊢ δ(q, εabb, Sbb) R2
⊢ δ(q, abb, abb) R3
⊢ δ(q, bb, bb) R4
⊢ δ(q, b, b) R4
⊢ δ(q, ε, z0) R5
⊢ δ(q, ε)
ACCEPT
EQUIVALENCE OF PDA AND CFG
Example-4:
Given CFG G:
I  a | b | Ia | Ib
E  I | E * E | E + E | (E)
Solution for PDA:
1. For Non-terminals
δ (q, ε, I) = {(q, a), (q, b), (q, Ia), (q, Ib)}
δ (q, ε, E) = {(q, I), (q, E*E), (q, E+E), (q, (E))}
2. For Terminals
δ (q, a, a) = {(q, ε)} δ (q, b, b) = {(q, ε)}
δ (q, (, () = {(q, ε)} δ (q, ), )) = {(q, ε)}
δ (q, *, *) = {(q, ε)} δ (q, +, +) = {(q, ε)}
Process the following strings using stack
1. (a+a)*(a*a) 2. a*a+((a))
EQUIVALENCE OF PDA AND CFG
PDA to CFG:
• Let M = (Q, Σ, Γ, δN, q0, Z0, φ) that accepts Language L = N(M) by empty
stack (If the PDA is accepting by final state, convert to empty stack then
proceed).
• Then, there exists a CFG that accepts L, such L = L(G)
• The non-terminals of G are symbols of the form [p X q]
• p, q ɛ Q and X ɛ Γ, and a start symbol S.
• [p X q] variable generates all and only the strings w such that
(p, w, X) ⊦*(q, ε, ε).
PDA to CFG
• Identify Non-Terminals
• For every pair of states, there will be a non-terminal with combinations of
Stack Symbols.
• Let as assume Q = {q0 , q1, q2} and Γ = {Z0, X} then
• [q0 Z0 q0], [q0 Z0 q1], [q0 Z0 q2]
• [q1 Z0 q0], [q1 Z0 q1], [q1 Z0 q2]
• [q2 Z0 q0], [q2 Z0 q1], [q2 Z0 q2]

• [q0 X q0], [q0 X q1], [q0 X q2]

• [q1 X q0], [q1 X q1], [q1 X q2]
• [q2 X q0], [q2 X q1], [q2 X q2]
PDA to CFG
How to write productions of G?
• Each production for nonterminal [p X q] comes from a move of M in state p with
stack symbol X.
Case 1: Writing the Production Rules for POP operations.
• δ(p, a, X) = (q, ε)
Production is : [p X q] -> a
• δ(p, ε, X) = (q, ε)
Production is : [p X q] -> ε
PDA to CFG
Case 2: Writing the Productions for single pop followed by single push
δ(p, a, X) = (r, Y) for some state r and symbol Y.
Production is :
[p X q] -> a[r Y q]
• Entering state r and replacing the X by Y and then reading some w that gets M
from r to q while erasing the Y.
• Note: [p X q] =>* aw whenever [r Y q] =>* w.
PDA to CFG
Productions of G:
Case 3: Writing the Productions for push operations
δ(p, a, X) = (r, YZ) for some state r and symbol Y and Z.

[p X q] -> a[r Y s][s Z q] for all states s.

[p X q] =>* awx whenever [r Y s] =>* w and [s Z q] =>* x.
PDA to CFG
Productions of G:
Case 3: Writing the Productions for push operations
Suppose δ(p, a, X) contains (r, Y1,…Yk)
for some state r and k > 3.

δ(p, a, X) = {(r, YZ)}

[p X _ ] → a [r Y _] [ _ Z _]
• Spaces (_) to be filled with states.
• These are variables, so format is [Variable Stack_symbol Variable]

[p X _] → a [r Y _ ] [ _ Z _]
Same
PDA to CFG
Productions of G:
Case 3: Writing the Productions for push operations
Suppose δ(p, a, X) = (r, Y1,…Yk)
for some state r and k > 3.

Generate family of productions

[p X q] -> a[rY1s1][s1Y2s2]…[sk-2Yk-1sk-1][sk-1Ykq]

Same
PDA to CFG
Productions of G:
Completion of the Grammar Construction:
To prove that (q0, w, Z0)⊦*(p, ε, ε) if and only if [q0 Z0 p] =>* w.
• Here, state p can be anything.
• Thus, add to G another variable S, the start symbol, and add productions S -> [q0
Z0 p] for each state p.
PDA to CFG a, Z0 → XZ0 ɛ, Z0 → ɛ
Example: a, X → XX b, X → ɛ

q0 b,X → ɛ q1

M = ({q0,q1}, {a, b}, {X, Z0}, δ, q0, Z0, φ)

(q0, aabb, Z0)⊦*(q1, ε, ε) if and only if [q0 Z0 q1] =>* w.
S → [q0 Z0 q0]
S → [q0 Z0 q1]
• Identify Non-Terminals: For every pair of states, there will be a non-terminal with
combinations of Stack Symbols.
• [q0 Z0 q0], [q0 Z0 q1],
• [q1 Z0 q0], [q1 Z0 q1],
• [q0 X q0], [q0 X q1],
• [q1 X q0], [q1 X q1]
PDA to CFG
Productions of G:
Writing the Productions for push operations
Suppose δ(p, a, X) = (r, Y1,…Yk)
for some state r and k > 3.
Generate family of productions
[p X q] -> a[rY1s1][s1Y2s2]…[sk-2Yk-1sk-1][sk-1Ykq]

Same
EQUIVALENCE OF PDA AND CFG
δ(p, a, X) = (r, YZ) then [p X q] -> a[r Y s][s Z q] for all states s.
[Here q can be q0, q1and s can be q0, q1]
1) δ(q0, a, Z0) = (q0, XZ0)
[q0 Z0 q0] → a [q0 X q0] [q0 Z0 q0] All Possible Combinations
[q0 Z0 q0] → a [q0 X q1] [q1 Z0 q0]
[q0 Z0 q1] → a [q0 X q0] [q0 Z0 q1] 3) δ(q0, b, X) = (q1, ε) [q0 X q1] → b
[q0 Z0 q1] →a [q0 X q1] [q1 Z0 q1]
2) δ(q0, a, X) = (q0, XX) 4) δ(q1, b, X) = (q1, ε) [q1 X q1] → b
[q0 X q0] → a [q0 X q0] [q0 X q0]
[q0 X q0] → a [q0 X q1] [q1 X q0]
5) δ(q1, ε, Z0) = (q1, ε) [q1 Z0 q1] → ε
[q0 X q1] → a [q0 X q0] [q0 X q1]
[q0 X q1] →a [q0 X q1] [q1 X q1]
Finding useful productions
Finding useful productions based on S
S → [q0 Z0 q0] – Not useful, Remove
S → [q0 Z0 q1] Since (q0, aabb, Z0)⊦*(q1, ε, ε) // (q0, aabb, Z0)⊦*(q1, ε, ε) if and only if [q0 Z0 q1] =>* w.
Since [q0 Z0 q0] is eliminated, productions involving in [q0 Z0 q0] on LHS or RHS can be removed.

[q0 X q1] → b [q0 Z0 q0] → a [q0 X q0] [q0 Z0 q0] - Remove [q0 X q0] → a [q0 X q0] [q0 X q0]
[q0 Z0 q0] → a [q0 X q1] [q1 Z0 q0] - Remove [q0 X q0] → a [q0 X q1] [q1 X q0]
[q1 X q1] → b
[q0 Z0 q1] → a [q0 X q0] [q0 Z0 q1] [q0 X q1] → a [q0 X q0] [q0 X q1]
[q1 Z0 q1] → ε [q0 Z0 q1] →a [q0 X q1] [q1 Z0 q1] [q0 X q1] →a [q0 X q1] [q1 X q1]
Finding useful productions
Finding useful productions based on only terminal or ε on RHS
[q0 X q1] → b
[q1 X q1] → b
[q1 Z0 q1] → ε
As non terminals [q0 X q1], [q1 X q1], and [q1 Z0 q1] are able to terminate.

Non terminals like [q0 X q0] are not able to terminate remove them if they are on LHS or RHS of
any production
S → [q0 Z0 q1]

[q0 Z0 q1] → a [q0 X q0] [q0 Z0 q1] - remove

[q0 Z0 q1] →a [q0 X q1] [q1 Z0 q1]

[q0 X q0] → a [q0 X q0] [q0 X q0] - remove

[q0 X q0] → a [q0 X q1] [q1 X q0] - remove
[q0 X q1] → a [q0 X q0] [q0 X q1] - remove
[q0 X q1] →a [q0 X q1] [q1 X q1]
Finding useful productions
S → [q0 Z0 q1]
[q0 Z0 q1] →a [q0 X q1] [q1 Z0 q1]
[q0 X q1] →a [q0 X q1] [q1 X q1]
[q0 X q1] → b
[q1 X q1] → b
[q1 Z0 q1] → ε

Let A = [q0 Z0 q1], B = [q0 X q1], C = [q1 X q1] D = [q1 Z0 q1]

SA
A  aBD
B  aBC / b
Cb
Dε
Construct PDA for no. of 'a’s > [Link] ‘b‘s and write CFG
Example: a, aab, aaaabbb

a, Z0 → XZ0 ε, Z0 → ε
Matching for a, X → XX ε, X → ε
a’s and b’s a, Y → ε
ε, X → ε q2
q1
Checking for more
a’s than b’s
b, Z0 → YZ0
b, Y → YY
b, X → ε
Convert the PDA M = ({q1, q2}, {a,b}, {X,Y,Z0}, δ, q1, Z0, φ) into CFG.
[q1Z0 -]  a[q1 X -][- Z0-]
Problems
Convert the following PDA M = ({q}, {0,1}, {Z, A, B}, δ, q, Z, φ) into CFG.
1. δ(q,0,Z)=(q, AZ)
2. δ(q,1,Z)=(q, BZ)
3. δ(q,0,A)=(q, AA)
4. δ(q,1,B)=(q, BB)
5. δ(q,1,A)=(q, ε) Solution
6. δ(q,0,B)=(q, ε) Start Symbol S→ [qZq] CFG,
7. δ(q, ε,Z)=(q, ε) 1. [qBq] →0 S → ε (3)
2. [qAq] →1 S →0AS (4)
3. [qZq] →ε S →1BS (5)
4. [qZq] →0[qAq][qZq] A →0AA (6)
5. [qZq] →1[qBq][qZq] B →1BB (7)
6. [qAq] →0[qAq][qAq] A →1 (2)
7. [qBq] →1[qBq][qBq] B →0 (1)
Non-deterministic PDA (NPDA) & Deterministic PDA ( DPDA)
Non-deterministic PDA (NPDA):
• An NPDA is a pushdown automaton where multiple transitions are possible for a
given input, stack symbol, and state. This means:
• The automaton may choose among different transitions.
• It accepts a string if at least one sequence of choices leads to an accepting state
or an empty stack.
Deterministic PDA
• A DPDA has at most one valid transition per input symbol, stack symbol, and
state. This means:
• It cannot "guess" the right path.
• It must have a unique transition for every input-symbol and stack-symbol pair.
• Not all context-free languages (CFLs) can be recognized by a DPDA.
Deterministic Pushdown Automata
A Pushdown Automaton (PDA) is deterministic if, for every possible configuration (state, input
symbol, and stack top), there is at most one possible transition. In other words, there is no
situation where multiple moves are possible.
• If δ(q, a, X) contains more than one pair, then PDA is non-deterministic
• If δ(q, a, X) is always a singleton, then have a choice between using a real input symbol,
or making a move on ε.
A PDA P = (Q, Σ, Γ, δ, q0, Z0, F) is deterministic, iff the following conditions are met
• δ(q, a, X) has at most one member for any q in Q, a in Σ or a = ε, and X in Γ
• δ(q, a, X) is nonempty, for some a in Σ, then δ(q, ε, X) must be empty

DPDA for L = {w|wcwR , w ɛ {0,1}*} [wcwreverse]

Deterministic Pushdown Automata
Deterministic Context Free Language (DCFL):
• A proper subset of context-free languages, which are the context-free languages that can be accepted
by a deterministic pushdown automaton.
• The Languages Accepted by DPDA’s:
• All the regular languages are accepted (by final state) by DPDA’s, and there are nonregular
languages accepted by DPDA’s.
• The DPDA languages are context-free languages, and in fact are languages that have
unambiguous CFG’s.
• Thus, the DPDA languages lie strictly between the regular languages and the context-free
languages.
• Expressive power of Automata: FA < DPDA < PDA
Two ways to build a CFG
Build a PDA Construct (indirect)
CFG from PDA

Derive CFG directly (direct)

Two ways to build a PDA

Derive a CFG Construct

PDA from CFG (indirect)

Design a PDA directly (direct)

Applications of FA
• For the designing of lexical analysis of a compiler.
• For recognizing the pattern using regular expressions.
• For the designing of the combination and sequential circuits using Mealy and
Moore Machines.
• Used in text editors.
• For the implementation of spell checkers.
Applications of PDA
• For designing the parsing phase of a compiler (Syntax Analysis).
• Yacc Parser Generator
• For implementation of stack applications.
• For evaluating the arithmetic expressions.
• For solving the Tower of Hanoi Problem.
• Matching a symbol with another symbol
• XML Programming
EQUIVALENCE OF PDA AND CFG
Example:

Case 1: Writing the Production Rules for POP operations.

If δ(p, a, X) = (q, ε) then [p X q] -> a Where a ε Σ U {ε }]
δ(q1, b, X) = (q1, ε), so [q1 X q1] → b
δ(q1, ε, Z0 ) = (q1, ε) [q1 Z0 q2] → ε
EQUIVALENCE OF PDA AND CFG
Case 2: Writing the Productions for single pop followed by single push
Case-2: δ(p, a, X) = (r, Y) for some state r and symbol Y.
Production is : [p X q] -> a[r Y q] [Here q can be q0, q1, q2]
δ(q0, ε, Z0) = (q1, Z0) δ(q0, ε, X) = (q1, X)
[q0 Z0 q0] → [q1 Z0 q0] [q0 X q0] → [q1 X q0]
[q0 Z0 q1] → [q1 Z0 q1] [q0 X q1] → [q1 X q1]
[q0 Z0 q2] → [q1 Z0 q2] [q0 X q2] → [q1 X q2]
EQUIVALENCE OF PDA AND CFG
Case 3: Writing the Productions for push operations
δ(p, a, X) = (r, YZ) then [p X q] -> a[r Y s][s Z q] for all states s.
[Here q can be q0, q1, q2 and s can be q0, q1, q2]
δ(q0, a, Z0) = (q0, XZ0)
[q0 Z0 q0] → a [q0 X q0] [q0 Z0 q0] |
a [q0 X q1] [q1 Z0 q0] |
a [q0 X q2] [q2 Z0 q0]
All Possible Combinations
[q0 Z0 q1] → a [q0 X q0] [q0 Z0 q1] |
a [q0 X q1] [q1 Z0 q1] |
a [q0 X q2] [q2 Z0 q1]
[q0 Z0 q2] →a [q0 X q0] [q0 Z0 q2] |
a [q0 X q1] [q1 Z0 q2] |
a [q0 X q2] [q2 Z0 q2]
EQUIVALENCE OF PDA AND CFG
δ(q0, a, X) = (q0, XX)
[q0 X q0] → a [q0 X q0] [q0 X q0] |
a [q0 X q1] [q1 X q0] |
a [q0 X q2] [q2 X q0]
All Possible Combinations
[q0 X q1] → a [q0 X q0] [q0 X q1] |
a [q0 X q1] [q1 X q1] |
a [q0 X q2] [q2 X q1]

[q0 X q2] → a [q0 X q0] [q0 X q2] |

a [q0 X q1] [q1 X q2] |
a [q0 X q2] [q2 X q2]
EQUIVALENCE OF PDA AND CFG
Final Grammar Productions are:
S → [q0 Z0 q2] [q1 X q1] → b [q1 Z0 q2] → ε

[q0 Z0 q0] → [q1 Z0 q0]

[q0 Z0 q1] → [q1 Z0 q1]
[q0 Z0 q2] → [q1 Z0 q2]

[q0 X q0] → [q1 X q0]

[q0 X q1] → [q1 X q1]
[q0 X q2] → [q1 X q2]

[q0 Z0 q0] → a [q0 X q0] [q0 Z0 q0] | a [q0 X q1] [q1 Z0 q0] | a [q0 X q2] [q2 Z0 q0]
[q0 Z0 q1] → a [q0 X q0] [q0 Z0 q1] | a [q0 X q1] [q1 Z0 q1] | a [q0 X q2] [q2 Z0 q1]
[q0 Z0 q2] →a [q0 X q0] [q0 Z0 q2] | a [q0 X q1] [q1 Z0 q2] | a [q0 X q2] [q2 Z0 q2]
[q0 X q0] → a [q0 X q0] [q0 X q0] | a [q0 X q1] [q1 X q0] | a [q0 X q2] [q2 X q0]
[q0 X q1] → a [q0 X q0] [q0 X q1] | a [q0 X q1] [q1 X q1] | a [q0 X q2] [q2 X q1]
[q0 X q2] → a [q0 X q0] [q0 X q2] | a [q0 X q1] [q1 X q2] | a [q0 X q2] [q2 X q2]
EQUIVALENCE OF PDA AND CFG
Input string: aabb
EQUIVALENCE OF PDA AND CFG
Identifying Useful Productions:
S → [q0 Z0 q2] [q1 X q1] → b [q1 Z0 q2] → ε

[q0 Z0 q0] → [q1 Z0 q0]

[q0 Z0 q1] → [q1 Z0 q1] Useless Variable / Production
[q0 Z0 q2] → [q1 Z0 q2]
Useful Variable / Production
[q0 X q0] → [q1 X q0]
[q0 X q1] → [q1 X q1]
[q0 X q2] → [q1 X q2]

[q0 Z0 q0] → a [q0 X q0] [q0 Z0 q0] | a [q0 X q1] [q1 Z0 q0] | a [q0 X q2] [q2 Z0 q0]
[q0 Z0 q1] → a [q0 X q0] [q0 Z0 q1] | a [q0 X q1] [q1 Z0 q1] | a [q0 X q2] [q2 Z0 q1]
[q0 Z0 q2] → a [q0 X q0] [q0 Z0 q2] | a [q0 X q1] [q1 Z0 q2] |a [q0 X q2] [q2 Z0 q2]
[q0 X q0] → a [q0 X q0] [q0 X q0] | a [q0 X q1] [q1 X q0] | a [q0 X q2] [q2 X q0]
[q0 X q1] → a [q0 X q0] [q0 X q1] | a [q0 X q1] [q1 X q1] | a [q0 X q2] [q2 X q1]
[q0 X q2] → a [q0 X q0] [q0 X q2] | a [q0 X q1] [q1 X q2] | a [q0 X q2] [q2 X q2]
EQUIVALENCE OF PDA AND CFG
Final Grammar Productions are:
S → [q0 Z0 q2]
[q1 X q1] → b
[q1 Z0 q2] → ε
[q0 Z0 q2] → [q1 Z0 q2]
[q0 X q1] → [q1 X q1]
[q0 Z0 q2] → a [q0 X q1] [q1 Z0 q2]
[q0 X q1] → a [q0 X q1] [q1 X q1]