Suppose I have a PDA $P$. What if I replace its First-In-Last-Out stack with a First-In-First-Out queue?

Is this new machine with a queue just as powerful as a PDA? Can it represent the same languages? I feel that it can because we can still count input with it. Does that make sense?

  • 5
    $\begingroup$ You get math.queueexchange.com. $\endgroup$ – Asaf Karagila Oct 21 '12 at 10:41

Yes. No. With a FIFO you even get a much more powerful machine, equivalent to a Turing machine. Intuitively, you are able to use the FIFO to "rotate" the information in it, so you can reach every position. That means you have in fact a Turing tape.

  • 2
    $\begingroup$ It seems to me that the answer to the OP's question is 'Yes, and in fact it is much more powerful', rather than 'No' (but with the same explanation). $\endgroup$ – Tara B Oct 19 '12 at 21:55
  • $\begingroup$ You are right, that seems better. I was a little overreacting to the "just as powerful". $\endgroup$ – Hendrik Jan Oct 19 '12 at 23:06

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.