GATE CSE 2015 | Set 3 | Question: 32

Question

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\}$

• A. $L_1$ and $L_2$ only
• B. $L_1$ and $L_3$ only
• C. $L_2$ and $L_3$ only
• D. $L_3$ only

Comments

https://youtu.be/ZSGsmg_9X4o?si=8NzCRLr9XhaTToB3

---

In L2 if we take a and skip b's then a will leads to straight comparison

Hence not CFL

Is my approach correct??

---

L2 : whenever there is a cross-comparison then its not CFL

---

If we can write the CFG for any language then it means that language is CFL so these are the CFG for the languages which are Context free.

L1:

S -> aSb | A

A -> bAa | ϵ

So we can write the CFG for L1 so it means L1 is CFL.

L2: L2 is not CFL because here first we push a in the stack as we have to remember the size of the a then we push b in the stack and will not pop a because we don't have to compare the size of a and b we have to compare the size of both a's and both b's, so we have to push b also into the stack then we reaches a & we have to pop a from the stack that we have pushed earlier but top of the stack is b so we can't pop so we can't compare the size of a and similarly for b, so that's why this language is not CFL

L3:  

S -> a | aaSb

So we can write the CFG for L3 so it means L3 is CFL.

So ans is option B - L1 and L3 only

 

Answer 1

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

Comments

Yes last approach was not correct but the approach I have given in this comment is correct i think - https://gateoverflow.in/8489/gate-cse-2015-set-3-question-32?show=434360#c434360

Approach - now first 'a' push and then skip one 'a' and continue. Now, for every 'b' pop one 'a' and if you will left with one 'a' in stack then it is valid otherwise not valid. 

take example "aab" now push first 'a' then skip one 'a' then for 'b' pop one 'a' now stack is empty so its invalid string.

---

Yes now correct : )

---

please explain L3 : if i put b into stack and skip 1 a's and for next 2a's pop 1 b's so stack will be empty at last so gives a CFL L3 is.

Answer 2

L1: First push all the a's in the stack then push all the b's in the stack. Now pop all the b's from the stack watching next no. of a's. And then pop all the a's from the stack watching next no. of b's. So can be done by PDA, hence CFL.

L2: First push all the a's in the stack then push all the b's in the stack. Now again a's come which cannot be compared by previous a's in the stack because at top of the stack's there are b's which is also needed to be pushed for further comparision with the next b's. So not CFL.

L3: First simply read one 'a', then push one 'a' in the stack after reading two a's and then pop all the a's by reading the b's. Since can be done by PDA hence CFL.
Option B

Comments

@varunrajarathnam

Sir, awesome approch for L3. Thanks

Answer 3

for L-3 Grammar should be like this ,

S -->aaSb | aaAb

A --> a

@GO Classes am i right.