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

So this is computationally equivalent to a Turing Machine, so in particular it can recognize $L = \{ww^R \mid w \in \{0, 1\}^*\}$.
• @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