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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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