4
$\begingroup$

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
    You get math.queueexchange.com.2012-10-21

1 Answers 1

3

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.

  • 0
    You are right, that seems better. I was a little overreacting to the "just as powerful".2012-10-19