UNIT 3

PUSHDOWN AUTOMATA
Pushdown Automata Definition
 Pushdown automata is a way to implement a CFG in
which it can remember an infinite amount of information.
 Pushdown automata is simply an NFA augmented with an
"external stack memory".
 Pushdown automata can store an unbounded amount of
information on the stack.
 It can access a limited amount of information on the
stack.
 A PDA can push an element onto the top of the stack and
pop off an element from the top of the stack.
 To read an element into the stack, the top elements must
be popped off and are lost.
Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 2
 Cont..
 PDA is more capable than Finite state machines and
less capable than Turing Machines.
 A PDA differs from finite state machine in two ways:
◦ It can use the top of the stack to decide which transition to
take
◦ It can manipulate the stack contents during the transition
Note:
A PDA is more powerful than FA. Any language
which can be acceptable by FA can also be acceptable
by PDA.
 PDA also accepts a class of language which even
cannot be accepted by FA. Thus PDA is much more
superior to FA. Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 3
Pushdown Automata - Components
 PDA = (ε-NFA)+stack.
 Input tape: The input tape is divided in many cells or symbols. The
input head is read-only and may only move from left to right, one
symbol at a time.
 Finite control: The finite control has some pointer which points the
current symbol which is to be read.
 Stack: The stack is a structure in which we can push and remove the
items from one end only. It has an infinite size. In PDA, the stack is
used to store the items temporarily.

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 4
Working of PDA
 PDA reads the input(one symbol at a time) from left to
right in the input tape
 Ineach step, based on the input symbol, current state
and the top of the stack the transition occurs.
 After consuming an input symbol, it may go to a new
state or remain in the same state.
 Replace the top of the stack by any string
◦ If the string is ε, then pop the element from the stack.
◦ It can be the same symbol of the stack (ie) no changes to
the stack.
◦ Replace the top stack symbol by another symbol which
changes the top of the stack
Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 5
Pushdown Automata
Formal Definition
The PDA can be defined as a collection of 7 components:
A PDA P can be defined as (Q, ∑, δ, Γ, Z ,q0, F), where
 Q: the finite set of states
 ∑: the input set
 δ: mapping function which is used for moving from
current state to next state.
 Γ: a stack symbol which can be pushed and popped from
the stack
 Z: a start symbol which is in Γ.
 q0: the initial state
 F: a set of final states

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 6
Transition Function
Current Next
State State

• On reading the input symbol ‘a’

δ(q0, a, Z) = (q0, aaZ) with top of the stack as z,
2 aa’s have been pushed into the stack.
Input Current Top New Top
Symbol of the stack Stack symbol

Push • On reading the input symbol ‘a’

δ(q0, a, a) = (q0, aaa)  with top of the stack as a,
2 aa’s have been pushed into the stack.

Pop • On reading the input symbol ‘b’

with top of the stack as a, the top most
δ(q0, b, a) = (q1, ε)  
symbol(a) is popped from the stack
Idle
• On reading the input symbol ‘c’
δ(q0, c, a) = (q0, a)  with top of the stack as a,
no operation is performed on the stack.
Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 7
Transition diagram
δ(qi, a, X) = (qj, Y)

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 8
Transition diagram
Stack Empty Push

Pop Idle

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 9
Instantaneous Description(ID)
 ID is an informal notation of how a PDA computes an input string and
make a decision that string is accepted or rejected.
 An instantaneous description is a triple (q, w, α) where:
 q describes the current state.
 w describes the remaining input.
 α describes the stack contents, top at the left.
Turnstile Notation:
 ⊢ sign describes the turnstile notation and represents one move.
 ⊢* sign describes a sequence of moves.
Eg: (p, b, T) ⊢ (q, w, α)
 In the above example, while taking a transition from state p to q, the
input symbol 'b' is consumed, and the top of the stack 'T' is
represented by a new string α.
Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 10
Language of PDA
A language can be accepted by PDA in
two ways.
◦ Acceptance by Final State
◦ Acceptance by Empty Stack
There are two types of PDA
◦ Deterministic PDA (DPDA)
◦ Non-Deterministic PDA (NDPDA / NPDA)

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 11
Acceptance by Final State
The PDA is said to accept its input by the final
state if it enters any final state in zero or more
moves after reading the entire input.
Let P =(Q, ∑, Γ, δ, q0, Z, F) be a PDA. The
language acceptable by the empty stack can be
defined as:
L(PDA) = {w | (q0, w, Z) ⊢* (p, ε, α), p ∈ F}

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 12
Acceptance by Empty Stack
On reading the input string from the initial
configuration for some PDA, the stack of PDA
gets empty.
Let P =(Q, ∑, Γ, δ, q0, Z, F) be a PDA. The
language acceptable by the final state can be
defined as:
L(PDA) = {w | (q0, w, Z) ⊢* (p, ε, ε), p ∈ F}

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 13
Deterministic PDA
A PDA is said to be deterministic if and
only if the following to conditions to be
satisfied.
◦ δ(q, a, X) has atmost one member for any q in
Q, a in ∑ or a= ɛ, and X in Γ.
◦ If δ(q, a, X) is not empty, for some a in ∑
then δ(q, ɛ, X) should be empty.

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 14
Deterministic PDA(DPDA)–Problem 1
Construct PDA for the language 𝑳 = {𝒂𝒎𝒃𝒏𝒄𝒎|𝒎, 𝒏
≥ 𝟎}
Description:
Step 1: Push all a’s onto the stack
Step 2: Don’t push b’s from tape onto the stack
Step 3: For every c’s in the tape, pop ‘a’ from the
stack

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 15
𝑳 = {𝒂𝒎𝒃𝒏𝒄𝒎|𝒎 >0, 𝒏 ≥ 𝟎}

a , a / aa c,a/ε

a , Z0 / aZ0 c,a/ε ε , Z0 / Z0
q0 q1 q3 q3

b,a/a
c,a/ε
q2

b,a/a

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 16
Deterministic PDA(DPDA)–Problem 2
ConstructPDA for the language 𝑳 = {𝒙 ∈ (𝒂, 𝒃)∗|
𝒏𝒂(𝒙) = 𝒏𝒃(𝒙)} or No. of a’s equal to No. of b’s.
Description:
Step 1: Push only a’s onto the stack
Step 2: For every b in the tape, pop ‘a’ from the
stack
Step 3: If the tape is empty and the stack is Z then
accept the string.

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 17
𝑳 = {𝒙 ∈ (𝒂, 𝒃)∗|𝒏𝒂(𝒙) = 𝒏𝒃(𝒙)}

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 18
Deterministic PDA – Problem 3
Is the PDA of the language L = {anbn  | n>=1} by the
finite state is deterministic ?
a , a / aa b,a/ε

a , Z0 / aZ0 b,a/ε ε , Z0 / Z0
q0 q1 q2 q3

Transition Function:
δ(q0, a, Z0) = (q1, aZ0)
δ(q1, a, a) =(q1, aa)
δ(q1, b, a) =(q2, ∈)
δ(q2, b, a) =δ(q2, ∈)
δ(q2, ∈, Z0) =δ(q3, ∈) Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 19
Problem 3
The PDA should satisfy the two conditions. shown
in the definition to be deterministic.
◦ δ(q0, a,  Z0) has only one element. In this case, for each
q∈Q, a∈∑ , and Z0∈Γ, there exists only one definition
for all the traansitions so the first condition is satisfied.
◦ To satisfy the second condition consider the transition
δ(q0, a, Z0) = (q1, aZ0) whis in non empty so that δ(q0, ∈,
Z0) is empty.
◦ Similarly for all other transitions also the second
coondition is satisfied.
Therefore the given language L = {anbn  | n>=1} is
deterinistic PDA. Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 20
Non-Deterministic PDA
The non-deterministic pushdown automata is
very much similar to NFA.
The CFG which accepts deterministic PDA
accepts non-deterministic PDAs as well.
Similarly,there are some CFGs which can be
accepted only by NPDA and not by DPDA.
Thus NPDA is more powerful than DPDA.

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 21
Non-Deterministic PDA
A PDA is non-deterministic, for the input
symbol and stack symbol, there is more than one
choice. Formally, NDPDA can occur in the
following cases:
◦ For the same stack symbol and same input symbol,
there is more than one choice.
◦ For the same stack symbol and one input symbol is ‘ɛ’
and other input symbol is S.
Note : The language accepted by Deterministic
PDA is not equivalent to the language accepted
by non-deterministic PDA. Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 22
Non-Deterministic PDA – Problem1
Construct PDA for the language 𝑳 = {𝒂𝒏𝒃𝒏| 𝒏≥ 𝟎}
Description:
◦ Step 1: Push all a’s onto the stack
◦ Step 2: For every b in the tape, pop ‘a’ from the stack
◦ Step 3: If the tape is empty and the stack is Z0 then
accept the string.

a , a / aa b,a/ε

a , Z0 / aZ0 b,a/ε ε , Z0 / Z0
q0 q1 q2 q3

ε , Z0 / Z0

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 23
 Cont..
Check whether the string ‘aaabbb’ is accepted
by the above PDA or not.
δ(q0,aaabbb,Z0) ⊢ δ(q1,aabbb,aZ0)
⊢ δ(q1,abbb,aaZ0)
⊢ δ(q1,bbb,aaaZ0)
⊢ δ(q2,bb,aaZ0)
⊢ δ(q2,b,aZ0)
⊢ δ(q2,ε,Z0)
⊢ δ(q3,ε,Z0)
Since it reaches the final state, the string is
accepted by the PDA.
Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 24
 Non-Deterministic PDA (NDPDA) –
Problem 2
Construct PDA for the language 𝑳={𝒂𝟐𝒏𝒃𝒏 | 𝒏 ≥ 𝟎}
Description:
Step 1: Push all a’s onto the stack
Step 2: For every b in the tape, pop two a’s from the
stack
Step 3: If the tape is empty and the stack is Z then
accept the string.

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 25
𝑳={𝒂 𝒃 | 𝒏 ≥ 𝟎}
𝟐𝒏 𝒏

a , Z0 / aa

a , Z0 / aZ0 b,a/ε
q0 q1 q2
ε,a/ε

0 / Z0
ε
,Z
0/

ε, Z
Z0

q3

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 26
Non-Deterministic PDA – Problem 3
 ConstructPDA for the language 𝑳 = {𝒙 ∈ (𝒂, 𝒃)∗ |
𝒏𝒂(𝒙) = 𝒏𝒃(𝒙)} or No. of a’s equal to No. of b’s.
Description:
 Step 1: Push only a’s onto the stack
 Step 2: For every b in the tape, pop ‘a’ from the stack
 Step 3: If the tape is empty and the stack is Z then
accept the string.

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 27
𝑳 = {𝒙 ∈ (𝒂, 𝒃)∗ | 𝒏𝒂(𝒙) = 𝒏𝒃(𝒙)}

a , Z0 / aZ0
a , a / aa
b,a/ε
b , Z0 / bZ0
b , b /bb
a,b/ε

ε , Z0 / Z0
q0 q1

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 28
Non-Deterministic PDA – Problem 4
 Construct Non-deterministic PDA for the language of
palindrome strings (both odd & even length) over (a, b)*.
Description:
 Step 1: Push a’s or b’s from the first half of the input onto
the stack.
 Step 2: Guess the middle symbol of the string non-
deterministically.
 Step 3: For every ‘a’ in the tape, pop ‘a’ from the stack and

 For every ‘b’ in the tape, pop ‘b’ from the stack
 Step 4: If the tape is empty and the stack is Z then accept
the string.
Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 29
PDA for the language of palindrome

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 30
EXAMPLE Problems for NPDA/ PDA
Odd length palindrome
Even length palindrome
Balancing Paranthesis
𝑳 = {𝒂𝒎𝒃𝒏𝒄𝒎|𝒎, 𝒏 ≥ 𝟎}
𝑳 = {𝒂𝒏𝒃𝒎𝒂𝟐(𝒎+𝒏)|𝒎, 𝒏 ≥ 𝟎}

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 31
Difference between DPDA & NPDA
DPDA NPDA

It is less powerful than NPDA. It is more powerful than DPDA.

It is possible to convert every DPDA It is not possible to convert every

to a corresponding NPDA. NPDA to a corresponding DPDA.

The language accepted by DPDA is The language accepted by NPDA is

a subset of the language accepted by not a subset of the language
NDPA. accepted by DPDA.

For each input symbol, from the

For each input symbol, from the
current state, there are multiple
current state, there is only one move.
moves.
a
a
a

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 32
CFG and PDA EQUIVALENCE

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 33
Conversion from CFG to PDA

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 34
Formal Conversion from CFG to PDA
Given : G= (V, T,P, S)
Output : PN= ({q}, T, δ, VUT, q, S)
Transition Function δ:
◦ For all A ∈ V, add the following transitions in
the PDA.
δ(q, ɛ, A)= (q, α) | where A → α in P.
◦ For all a ∈ T, add the following transitions in
the PDA.
δ(q, a, a)= (q, ɛ)

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 35
Conversion from CFG to PDA–Problem 1
CFG : G= {(S,A), (0,1),P, S)
S →AS | ɛ , A → 0A1 | A1 |01 and check whether
0011 is accepted by PDA or not.
PDA : P =({q}, {0,1}, δ, (S,A,0,1}, q, S)
Transition Function δ:
For Variables:
R1: δ(q, ɛ, S)= {(q, AS), (q, ɛ)}
R2: δ(q, ɛ, A)= {(q, 0A1), (q, A1),(q,01)}
For Non-terminals:
R3: δ(q, 0, 0)= (q, ɛ)
R4: δ(q, 1, 1)= (q, ɛ)
Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 36
Conversion from CFG to PDA–Problem 1

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 37
Conversion from CFG to PDA–Problem 1
δ(q, ɛ, S) ⊢ δ(q, 0011, S)
⊢ δ(q, 0011, AS) R1
⊢ δ(q, 0011, 0A1S) R2
⊢ δ(q, 011, A1S) R3
⊢ δ(q, 011, 011S) R2
⊢ δ(q, 11, 11S) R3
⊢ δ(q, 1, 1S) R4
⊢ δ(q, ɛ, S) R4
⊢ δ(q, ɛ, ɛ ) R1
Since both input and stack is empty the string is
accepted.
Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 38
Conversion from CFG to PDA

1.

2.

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 39
 Conversion from PDA to CFG
Theorem: If L is a language for some PDA,
then prove that there is an equivalent CFG
G accepting the language L.
Proof:
◦ Let PDA P be defined by (Q, ∑, δ, Γ,q0, F , Z0 )
◦ Assume if L is a CFL then there must be a CFG
G corresponding to L and is defined by 4
tuples(V, T, P, S).
◦ From the PDA the CFG can be constructed as
follows:
◦ N= {S,[p,A,q] where p,q ∈ Q, A ∈ Γ
◦ T= ∑ Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 40
The productions P for the start symbol S
and all the non-terminals can be defined
by the following rules::
1. For the start symbol, the production is
S →[q0,Z0,q]
2. For any transition function is in the form of
δ(p,a,A) = (q, ɛ), then the production is
[p,A,q] → a
3. For any transition function is in the form of
δ(p,a,A) = (q, β1 β2), then the production is
[p,A, qn] → a[q , β1, qn+1][qn+1, β2,qn]

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 41
Conversion from PDA to CFG
Convert the PDA P=({p,q}, {0,1},
{X,Z0}, δ, q, Z0) to a CFG if δ is given
by
δ(q,1,Z0) = (q,XZ0)
δ(q,1,X) = (q,XX)
δ(q,0,X) = (p,X)
δ(q, ɛ,X) = (q, ɛ)
δ(p,1,X) = (p, ɛ)
δ(p,0,Z0) = (q,Z0)

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 42
 Solution:
 CFG =( V,T,P,S)

 V=(S, [q,Z0,q] , [q, Z0,p], [q,X,q], [q,X,p],

[p,Z0,q] , [p, Z0,p], [p,X,q], [p,X,p])

 T= {0,1}

 S – Start Symbol

 (Note: For creating variables make all possible combination of

pair of states from Q along with each stack symbol. Here there

are only two states whose pairs are [q,q], [q,p], [p,q], [p,p] and

stack symbols are X, Z0 . So the variables become [q,Z0,q],

[q,Z0,p], [p,Z0,q], [p,Z0,p], [q,X,q],[q,X,p],

[p,X,q], [p,X,p].
Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 43
Productions for start Symbool S
◦ P1: S → [q,Z0,q]
◦ P2: S → [q,Z0,p]
Note: q- initial state Z0- initial stack symbol,
q,p – all states in Q.
δ(q,1,Z0) = (q,XZ0) (push operation)
Same state

◦ P3: [q,Z0,q] →1[q,X,q] [q,Z0,q]

◦ P4: [q,Z0,q] →1[q,X,p] [p,Z0,q]
◦ P5: [q,Z0,p] →1[q,X,p] [p,Z0,p]
◦ P6: [q,Z0,p] →1[q,X,q] [q,Z0,p]

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 44
δ(q,1,X) = (q,XX)
◦ P7: [q,X,q] →1[q,X,q] [q,X,q]
◦ P8: [q,X,q] →1[q,X,p] [p,X,q]
◦ P9: [q,X,p] →1[q,X,p] [p,X,p]
◦ P10: [q,X,p] →1[q,X,q] [q,X,p]
δ(q,0,X) = (p,X)(idle)
Same state

◦ P11: [q,X,q] →0[p,X,q]

◦ P12: [q,X,p] →0[p,X,p]
δ(q, ɛ,X) = (q, ɛ)(pop operation)

◦ P13: [q,X,q] →ɛ
Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 45
δ(p,1,X) = (p, ɛ)
◦ P14: [p,X,p] →1
δ(p,0,Z0) = (q,Z0)
◦ P15: [p,Z0,q] →0[q,Z0,q]
◦ P16: [p,Z0,p] →0[q,Z0,p]
Thus the PDA has been converted to CFG with 16
productions.

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 46
 Pumping Lemma for CFG
If L is a context-free language, there is a pumping
length p such that any string w ∈ L of length ≥
p can be written as w = uvxyz, where vy ≠ ε, |vxy| ≤
p, and for all i ≥ 0, uvixyiz ∈ L
Pumping lemma is used to check whether a
grammar is context free or not.

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 47
Steps involved in pumping lemma
1. Assume the language is in CFL.
2. Take a string z from CFL.
3. Find |z|≥n
4. Split z into uvwxy
i) |vwx|≤n
ii)|vx|≥ 1
iii) For all i>0, uviwxiy is in L.

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 48
1. Prove L={anbncn |n≥0} is not a CFG.
Solution:
2. Assume the language is in CFL.
3. Take z= anbncn
4. |z|≥n, n+n+n ≥ n, 3n ≥ n
5. z= anbncn
uvwxy= anbncn
u = an , vwx = bn ,y=cn
i) |vwx|≤n,
|bn| ≤n
n≤n
ii. |vx|≥ 1, vx= bn-m, n>m
| bn-m | ≥ 1
n-m ≥ 1 Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 49
 iii) uviwxiy = uvvi-1wxxi-1y
= uvwx(vx i-1)y
uviwxiy = an bn (bn) i-1cn
For i=0, uviwxiy = an bn (bn-m) 0-1cn
= an bn (bm-n) cn
= an bm cn is not in CFL.
For i=1, uviwxiy = an bn (bn-m) 1-1cn
= an bn cn is in CFL.
For i=2, uviwxiy = an bn (bn-m) 2-1cn
= an bn (bn-m) cn
= an b2n-m cn is not in CFL
Therefore, the given language is not in CFL.
Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 50
2.Prove L={0n | where n is prime} is not a CFG.
Solution:
1. Assume the language is in CFL.
2. Take z= 0n
3. |z|≥n, n ≥ n
4. z= 0n
uvwxy= 0n
u = 0q , vwx = 0r ,y=0n-(q+r), vx=0s
i) |vwx|≤n, | 0r | ≤n, r≤n
ii) |vx|≥ 1, vx= 0s ,s>0
| 0s | ≥ 1
s≥1
Prepared by S.S.KIRUHTIKA, AP/CSE,
SRM IST, RAMAPURAM 51
iii) uviwxiy = uvvi-1wxxi-1y
= uvwx(vx) i-1y
uviwxiy = 0q 0r(0s) i-10n-(q+r) = 0si-s+n
For i=0, uviwxiy = 0-s+n
= 0n-s is not in CFL.
For i=1, uviwxiy = 0n is in CFL.
For i=2, uviwxiy = 0s+n is not in CFL
Therefore, the given language is not in CFL.

Prepared by S.S.KIRUHTIKA, AP/CSE,

SRM IST, RAMAPURAM 52