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

• Your question was so badly phrased it made no sense at all. I edited into a form that be answered. Commented Oct 25, 2016 at 22:19
• Commented Oct 25, 2016 at 22:20
• And How can one simulate a PDA with a FIFO queue PDA? seems relevant to. Commented Oct 26, 2016 at 12:09

1 Answer

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 ? Commented Oct 25, 2016 at 16:09
• One more query - what if the language was L = { WW | W belongs to (0,1)* } ? Commented Oct 25, 2016 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$.
– MT_
Commented Oct 25, 2016 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? Commented Oct 25, 2016 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. Commented Oct 25, 2016 at 22:23