Which of the following is CSL?

Question

Comments

B is ans?

---

how do you say so?

---

^bcoz it is nt cfl as i m thinking
what urs

---

A &C are also not cfl right?

---

A nd C r cfl

---

I got how A will be CFL but how can C be CFL?

First we can insert 0s and pop 1s then we have traverde over m 0s, but now, we donot have any facility to check m value right?

Please correct me if I am wrong.

---

^ how A is CFL?

---

@sudsho first we push all o^s so we have m+1 zero in stack 
now for first time 1 pop a zero so we have now m o^s on stack nd n 1^s in i/p string 
now push all 1 so we have m+n 0 nd 1 on stack now for all next 0s in i/p pop all 0 nd 1s of stack nd now it is empty stack.

---

$0^{m+1} 1^{n+1} 0^{n+m}$

We can push 0s into stack and when we encounter 1 we have to pop one 0 and push 1s onto the stack. Now when we encounter 0, pop one 1 and then pop the top of the stack for each 0 encountered, if stack is empty and if there is no input character left, then we can accept the string else reject it.

OR

push 0s and 1s ,then pop the top of the stack for each 0 encountered, if the stack is left with 2 0s then we can accept the string else reject it.

---

yes..is c also CFL @saurabh?

---

for C assume m=1 forever....

---

we don't have anything to compare value of m right?

---

yes
it is cfl
so i think B is Csl

---

@saurabh  how will 00011100 be accepted then?

---

B and C  - CSL.  

A - CFL.

---

yes..c option is nt CFL...we cant fix m as 1 else after 1 we cant have more than one 0..which shouldnt be the case
here we can only match (m+n)0s for (m+n) 1s..after this nothing will remain on the stack to compare with m 0s...its CSL..

---

srry
u r right... my mistake...

---

So, may be the options are wrong?!

---

^agree with vijay....