TOC-QUEUE

Question

L={WW|W belongs to (0+1)⁺}
in machines where stack is used is replaced by a queue which supports insert and delete operations.. then the above language is?
1)regular
2)DCFL
3)CFL
4)CSL
************************************************
i think its CFL but not DCFL.. whenever input is equal to front of the queue, we keep deleting contents of queue and keep moving the input pointer  untill input is being equal to front,finally queue shud be empty. And this shud be done non deterministically.

 

Comments

it is CSl

AND given setup is turing Machine

So, it should be DCFL

---

sorry,i dint get you... at each statement you said differet things. can you please explain.. and how it is turing machine? you can go back and front on input tape without loosing the symbols on tape.. but in queue how do u get it back once u delete a symbol in queue.

Answer 1

Using queue we can achieve the same functionality for the language L = WW as the language L = W.W^R is simulated using a stack . But we don't know with confidence that where the first half will be completed. So it is also showing non deterministic behavior.

Hence the given language using a queue can be referred a CFL but not DCFL..