0
$\begingroup$

Consider the language of even-length palindromes $L = \{ WW^R \mid W \in \{0,1\}^* \}$. This language is surely context free and I need an NPDA to recognize it.

But, what if we replace the stack with a queue which supports insert and delete operations? Can a queue automaton accept $L$?

Improve this question
$\endgroup$
3

1 Answer 1

Reset to default
9
$\begingroup$

The construction of a PDA except with a FIFO instead of a LIFO data structure attached can mimic any single tape TM as follows: it keeps the cell contents in the queue along with two special markers for the end of the tape and for the head of the TM. Every time you make a move, you just go through the entire queue and re-push everything you pop, making whatever slight modification in head position and tape contents you require.

So this is computationally equivalent to a Turing Machine, so in particular it can recognize $L = \{ww^R \mid w \in \{0, 1\}^*\}$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for the answer ! Can you elaborate more on the part how it mimics TM ? $\endgroup$
    – Garrick
    Oct 25, 2016 at 16:09
  • $\begingroup$ One more query - what if the language was L = { WW | W belongs to (0,1)* } ? $\endgroup$
    – Garrick
    Oct 25, 2016 at 16:23
  • $\begingroup$ @Willturner I Think filling in the details will be a good exercise. As per the second question, the answer is of course yes -- we can easily design a TM (with multiple tapes perhaps to make it even easier; $k$-tape TMs and single-tape TMs define the same class of languages) that accepts $L$. $\endgroup$
    – MT_
    Oct 25, 2016 at 17:57
  • $\begingroup$ Okk , I'll see that in detail. Just a doubt - Is it ok, to say that queue automaton recognizes this language and hence it is Recursively enumerable language and not CFL, which it was before when we used stack? $\endgroup$
    – Garrick
    Oct 25, 2016 at 19:19
  • 1
    $\begingroup$ " Is it ok, to say that queue automaton recognizes this language and hence it is Recursively enumerable language and not CFL, which it was before when we used stack? " -- no, not at all. The definition of CFL does not change just because you investigate some other machine model. $\endgroup$
    – Raphael ♦
    Oct 25, 2016 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.