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

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

with all due respect, ur explanation is a little bit wrong, bcz we cannot pop to symbols at one, we can push multiple but pop only one, so L3 will be like a.a^n.b^b where in case of a we skip one a and push other a , then pop a for ever b, hence this way L3 will be designed.

---

Alternate power comparison is CSL. Thus $L_2: \left\{a^mb^na^mb^n \mid m, n \geq 1\right\}$ is not CFL.

---

we can pop multiple symbols by using a cycle in the PDA.

correct me if am wrong

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