GATE CSE 2006 | Question: 19

Question

Let

$L_1=\{0^{n+m}1^n0^m\mid n,m\geq 0 \}$,

$L_2=\{0^{n+m}1^{n+m}0^m\mid n,m\geq 0\}$ and

$L_3=\{0^{n+m}1^{n+m}0^{n+m}\mid n,m\geq 0\} $.  

Which of these languages are NOT context free? 

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

Comments

Alternate reasoning for why L2 is not CFL

Let us assume that L2 is CFL => There exists a PDA which recognizes this language => The working of the PDA will be $0^{m+n} 1^{m+n}$ will match with each other and we can have m number of 0’s in the end.

This PDA will accept any strings of the form $0^{n+m}1^{n+m}0^m$. 

Contradiction

This same PDA will also accept 00110000 (if you draw the above PDA), but it should be rejected because this string does not belong to the language. So this language is not CFl and there does not exists a PDA for it.

---

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

---

Question starts at 35:08

Answer 1

Answer is (D)

$L_1$ is context-free. We count the number of $0$'s and check if the remaining number of $1$'s followed by 0's count to the initial number of $0$'s.

$L_2$ is not context-free. Here the number of $0$'s and the following $1$'s must be same, which can be checked using a PDA. But after that we must also ensure that the following number of $0$'s must be less than the previous count of $0$'s and $1$'s (otherwise $n < 0$, which violates the condition for acceptance) and we cannot do these two checks using a single PDA.

$L_3$ is again not context-free as it is nothing but equal number of $0$'s followed by equal number of $1$'s followed by equal number of $0$'s.

Comments

L1 is CFG. Since , we can push all 0’s until 1 arrives then start poping 0’s , on arrivinngg of first 0 change state and pop further.

---

$L_{1}$ is CFL since after pushing $0’s$ we can pop when $1$ arrives.

$L_{2}$ not CFL since here equal no. of $0’s$ and $1’s$. But we have to ensure that following $0’s$ must be lesser than count of $0’s$ $1’s$ and it is not possible in single PDA. Here need 2 stacks

$L_{3}$ not CFL as here $0’s$ count equal to followed by no. of $1’s$ which is equal to following $0’s$ count. In a single PDA we can’t keep record. here again need 2 stacks.

---

thank you..

Answer 2

Take language one by one:

1. L1 is CFL Even DCFL since push all 1's , when first 0 come start pop untill stack is empty.Take language one by one:
2. L3 is Non -CFL Even DCFL since push all 0's , when first 1 come start pop untill stack is empty, now at this point you forget what is the value of m+n since stack is empty So you need two stacks . if you took n+m=p then language look like  .
3. L2 is Non-CFL since  push all 0's , when first 1 come start pop untill stack is empty, now at this point you forget what is the value of m since stack is empty So you need two stacks .

Comments

@mesh90

It will accept those strings also which are not part of the language according to that logic. And if you are satisfied with $L_{3}$ then when you put n=0 in $L_{2}$ you will get $0^m1^m0^m$ which is same as $L_{3}$. Hence not CFL.

---

What do you mean by L3 is Non -CFL Even DCFL 

---

DOUBT:can’t we just skip the remaining zeroes in L2 and L3? so in order to get accepted by the PDA?

my reasoning : we cant skip the remaining zeroes because of the unknown’s n and m ..as all the comparisons between 0 and 1 are based on the n and m .(so as to avoid invalid string getting accepted by PDA)

is my reasoning correct???

Answer 3

L1 can be accepted by PDA, we need to push all 0’s before 1’s and when 1’s comes in input string we need to pop every 0’s from stack for every 1’s and then for every 0’s. If stack and input string is empty at the same time then the string belongs to L1.

But for L2 and L3 PDA implementation is not possible. The reason is, in L2 there are two comparison at a time, first the number of 0’s in beginning should be equal to 1’s and then 0’s after 1’s must be less than or equal to number of 1’s. Suppose for initial 0’s and 1’s are matched by using stack then after matching stack will become empty and then we cannot determine the later 0’s are equal to or less than number of 1’s.

Hence PDA implementation is not possible.

Similarly L3 also has the similar reason.
Option D is right.

Comments

Nice explanation!

Answer 4

L2 and L3 are  like  language  a^nb^nc^n. which is csl . because there is two comparision so we cannot drow PDA .

Comments

What is wrong with my argument? Why is it invalid?

---

Wrong.

L2={ a$^{n}$b$^{n}$c$^{p}$ | p<=n and p,n>=0 }

---

raja11sep

if this is the case then why isn’t it CFL?

---

You need to keep track of the number of a's and b's while also making sure that c is not more than a/b which is not possible using a single stack; now imagine using two stacks; push a's in both the stack; pop 'a' from one for every 'b' and pop 'a' from other stack for every 'c' this way you can keep track of both the things

Answer 5

for  the first one I can construct a grammar like this;
S->0S0|EPSILON|A
A->0A1|EPSILON
so this  is context free.

For the second one to construct it we need an npda with 2 stacks.
 Or we can argue like this that if n=0 then the resulting language becomes a^n b^n c^n which is not a cfg.

for the third one it is exactly like :
a^n b^n c^n which is not a CFG.

Answer 6

L1 can be accepted by PDA, we need to push all 0’s before 1’s and when 1’s comes in input string we need to pop every 0’s from stack for every 1’s and then for every 0’s. If stack and input string is empty at the same time then the string belongs to L1.
But for L2 and L3 PDA implementation is not possible. The reason is, in L2 there are two comparison at a time, first the number of 0’s in beginning should be equal to 1’s and then 0’s after 1’s must be less than or equal to number of 1’s. Suppose for initial 0’s and 1’s are matched by using stack then after matching stack will become empty and then we cannot determine the later 0’s are equal to or less than number of 1’s. Hence PDA implementation is not possible. Similarly L3 also has the similar reason.