# Can a queue automaton recognize palindromes?

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$?

– Raphael
Oct 25 '16 at 22:19
• – Raphael
Oct 25 '16 at 22:20
• And How can one simulate a PDA with a FIFO queue PDA? seems relevant to. Oct 26 '16 at 12:09

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\}^*\}$.

• Thanks for the answer ! Can you elaborate more on the part how it mimics TM ? Oct 25 '16 at 16:09
• One more query - what if the language was L = { WW | W belongs to (0,1)* } ? Oct 25 '16 at 16:23
• @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$.
– MCT
Oct 25 '16 at 17:57
• 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? Oct 25 '16 at 19:19
• " 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.
– Raphael
Oct 25 '16 at 22:23