The Gateway to Computer Science Excellence
+37 votes

Which of the following languages are context-free?

$L_1: \left\{a^mb^na^nb^m \mid m, n \geq 1\right\}$

$L_2: \left\{a^mb^na^mb^n \mid m, n \geq 1\right\}$

$L_3: \left\{a^mb^n \mid m = 2n +1 \right\}$

  1. $L_1$ and $L_2$ only
  2. $L_1$ and $L_3$ only
  3. $L_2$ and $L_3$ only
  4. $L_3$ only
in Theory of Computation by
edited by | 5.5k views

1 Answer

+48 votes
Best answer

first check for $L_1$. now look $a^m$ & $b^m$ and $a^n$ & $b^n$ must $be$ comparable using one stack for CFL.
now take a stack push all $a^m$ in to the stack  then push all $b^n$ in to stack now $a^n$ is coming so pop $b^n$ for each $a^n$ by this $b^n$ and $a^n$ will b comparable. now we have left only $a^m$ in stack and $b^m$ is coming so pop $a^m$ for each $b^m$ by which we can compare $a^m$ to $b^m$ ..we conclude that we are comparing this $L_1$ using a single stack so this is CFG.

now for $L_2$.this can not be done in to a single stack because $m$ and $n$ are not comparable we can not find when to push or  pop so this is CSL.

now for $L_3$.push all $a$'s into stack and pop $2a$ 's for every $b$  and at last we left with a single $a$ .
bcz here $aaaaabb$ is a valid string where $m=2n+1$ and $n=2$. So realized using single stack hence $L_3$ is CFG.

so the option is B.. $L_1$ and $L_3$ are CFG

edited by


sorry it is little bit confusing. "GATE FORUM Engineering Success" replies this question the correct is option (C) with explanation as given below :

Exp: L: {ambnanbm} This one is CFL
L2 : {ambnambn } by pumping lemma this one is not CFL.
L3 : {ambn }  ;m = 2n +1 This is CFL.

Where as your above explanation show correct option is (B) which contradicts each other. please explain. so that the readers may be able to understand the correct answer.

The explanation given is L1 and L3 only are CFL rt? So, where is the contradiction?

And from GATE 2012 on wards just look at official answer keys.


L2  ={ambnambn  | m,n >=1 }      , the language L2 can be implemented by PDA using single stack... We can push all a's and all b's ,this covers first two ambn .. After doing so when 'a' appears go on doing pop action and again when 'b' appears do pop action again.. Since the sum of the indices m and n in first two is equal to m and n of the third and fourth.., so total number of push will be equal to total number of pop.. And concequently at the end the stack will be emply...

For example let m= 3      n= 2    So m+n= 5 ,     We push 3 a's and then push again 2 b's ... Thereafter when                  

'a' appears pop again then 'b' appears pop... Total number of push = total number of pop = 5   And the stack will be empty... So we construct PDA.. Therefore the L2 is CFG.....

So option (a) is correct L1 is no doupt correct... 

Kindly comment if i am wrong...


a2b3a1b4 not belong to the language . first check the string belong to the language. its not a+b= a+b

a2b3a1b  In this example... Power of 'a' and 'b' is not same... But the language L2 says that power of first 'a' is same as power of second 'a' and same for 'b'.... So the given string is not part of the L2 ...

yes but your approach "m+n" = "m+n" is accepting this string, right?
0 approach accept this string.... The L2 says that first number of  first a' s is equal to number of a's that starts at third place... A d b's also same at both places.. By following these step , we get the emply stack... So L2 is accpeted by PDA...
is it right if it is accepting the string which does not belong to language? look here u need to know no of a's = no of a's and no b's= no b's. but when u will add both a+b then how u will say that first a and second a , 1st b and 2nd b  are equal. you are saying first half and second half is equal which doesn't belong to our language.
@Lubna you can count only one at a time.

@arjun sir Plz see the ans.

"now for L3. push all a's into stack and pop a single a for every 2b"

i think it should be push all a's into stack and pop 2a 's for every b  and at last we left with a single a .

bcz here aaaaabb is a valid string where m=2n+1 and n=2

plz correct me !

yes, we would never insert 'b's right?
$L_2$ is CSL, popularly knows as language for matching formal and actual parameters for programming languages.
@sachin see my comment here
@Arjun sir, What if we have m<>n in L1? Then what language would it be?
so, L3 is acceptance by final state using PDA (1 stack)
is it really possible to pop two symbols at a time?

(in above case you said pop 2 a’s for 1 b)

Bhai aap ladki hote to mera crush jarur hota :D

b is answer only if N > 1

For L3, where the number of a's are 2n + 1, where n represents the number of b's.

Pushing all the a's on the stack and then popping two a's for every b, the last a is popped by the epsilon and finally, the string is accepted by looking at the bottom of the stack by this logic the PDA is 

But, I have a doubt, we can only see one symbol in the top of the stack, so by seeing one symbol can we remove two symbols? Or, is the working shown in the PDA valid?


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,498 answers
95,322 users