Ace test Series

Question

Which of the following is CSL?

Comments

@ vishwa in your explainatin, why are you saying that we need two stacks? What is the problem in single stack?

---

I can push any amount of M after N or vice versa in one stack but when i need comparison of anyother variable say L , then we need one more stack as we cnt do comparision just with the previous stack.

---

Sorry, but I am not getting exactly what you are saying, so try to tell the problem in the following steps.

Take one stack.

Dont push first 0 and then push rest of the 0's.

Dont push first 1 and then push rest of the 1's.

Now with every occurence of 0, do a pop.

If at last, string is ended, and we get empty stack, then string is accepted, otherwise not.

TADA!! done in single stack.

Where is the problem?

Answer 1

All of them are Context Sensitive.

Option A , For one 0 donot push anything to stack and then for all 0 push it into the stack , same with 1 , for 1st 1 donot do anything and from rest start pushing it into stack , and for every zero now pop out 0 and 1.

here we require 2 stacks for storing the info of first 0 and 1 , and one more stack for comparing , so it is CSL.

Option B , for all 0 push them into stack , and for 1 push them into stack and pop out 0 after all 0 are poped out push 1's. Now to push 0 we require here comparision with m , but we have poped them out , so we would need atleast 3 stack.

Option C again we need 3 stacks at min.

so all are CSL , let me know if i am wrong.

Comments

We never ever require 3 stacks for anything. FA+2 stacks is turing machine. Adding any number of resources further will not increase the power as well as not needed.

Key point:

Fa+2 stacks= Fa+3 stacks

Answer 2

I think the ans is B

A.

for the first 0 dont push any stack symbol, start pushing 0 after that. similarly for the first 1 dont push any stack symbol , start pushing one 1 after that. Now simply pop the stack for every 0 . Thus its a CFL

C.  is recursive as for every m+n there should exist a point in grammer which can identify m which is to be used by 0 at last. I AM NOT SURE OF THIS.

B. we know that 0^n 1^n 0^n  is CSL we just need to add a production which produces any number of ones in addition to n number of 1s therefore producing m+n 1s.

Therefore I think B is a CSL

Answer 3

If this is standard question then we must find the language which is CSL and Not CFl because we look for most restrictive case.

option A: push 0 then do nothing on last 0 , now push 1 and do nothing on last 1,now pop 1 from 0 until we get 0 on top of stack then again pop 0 by looking 0 on top of stack until we get empty stack. so it is CFL since it is accepted by single stack.

option C : push 0 then pop 0 by looking 1 until we get empty stack and then do nothing on looking last 0^m. so accepted again by single stack.

Option B : push 0 then pop 0 by looking 0 until we get empty stack (for first half 0^m 1^m)....but now there is no way to count last 0^m in this stack because we have already popped off all elements from stack. thus it can not be accepted by single stack .....Not CFL and it can be accepted by two stacks because two comparisons are required ..thus it is CSL.

Option B is correct

Comments

A is DCFL ryt..only one PDA is enough to do this

---

yes it can be accepted by DPDA thats why it is DCFL.