Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
You get – Asaf Karagila Oct 21 '12 at 10:41
up vote 3 down vote accepted

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.

share|cite|improve this answer
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). – Tara B Oct 19 '12 at 21:55
You are right, that seems better. I was a little overreacting to the "just as powerful". – Hendrik Jan Oct 19 '12 at 23:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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