3
$\begingroup$

I'm trying to figure out how a pushdown automata (PDA), which we know uses a stack (LIFO) can be simulated by a queue (FIFO). I understand that in a regular PDA, we only have access to the top most element which can be popped. When we push something, it goes to the top of the stack.

In a queue, as I understand, elements get "pushed" to the top, but pop from the bottom. Thus, first in first out.

In a stack (LIFO) PDA, let's say we push 'a'. It's at the top of the stack, and when we pop, we pop 'a' since it is at the top.

In a queue (FIFO) PDA, when we push 'a', it is at the top, but when we pop, it will be from the bottom of the queue and thus it will not be 'a' (assuming the size is greater than 2).

So how can we simulate a regular PDA which uses a stack, with a FIFO (queue) PDA?

Improve this question
$\endgroup$
3
  • $\begingroup$ Are you limited to one queue? It's relatively easy with two. $\endgroup$
    – Luke Mathieson
    Nov 29, 2012 at 1:01
  • $\begingroup$ Not limited to one queue. $\endgroup$
    – San
    Nov 29, 2012 at 1:03
  • 1
    $\begingroup$ You may be interested in our thoughts on heap automata. $\endgroup$
    – Raphael ♦
    Nov 29, 2012 at 16:47

1 Answer 1

Reset to default
7
$\begingroup$

The answer is: "rotate".

Consider the stack like (bottom) ABCD (top). stack-pop is from top, queue-pop is from bottom (this is directed to myself, I am easily confused). Pushes are from top.

Now, if we want to stack-pop, we push a marker # (to top) then repeatedly queue-pop and push, essentially moving everything from bottom to top. If we delay the pushes by one, we are able to stack-pop, just not pushing the last symbol before the #.

By the way, almost the same trick shows that we can even simulate the Turing machine by a single queue. Which was asked in our sister math department.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Does this also mean if there's a PDA with 2 stacks (LIFO), we can simulate it with just 1 queue (FIFO)? $\endgroup$
    – San
    Nov 29, 2012 at 1:36
  • $\begingroup$ Indeed we can. Just keep track of where the stacks are, using markers, and with rotations we can reach every position. Intuitively, one queue equals two stacks equals a Turing machine. $\endgroup$
    – Hendrik Jan
    Nov 29, 2012 at 1:40
  • $\begingroup$ If you allow arbitrary rotation, you may as well use a Turing machine tape... $\endgroup$
    – Raphael ♦
    Nov 29, 2012 at 16:47
  • $\begingroup$ Sorry if I misunderstand you, but I am just using a FIFO queue. Which can simulate a TM tape. The regular queue operations allow me to rotate, step by step. A marker is neede to signal when I return, so I can stop in time. That makes a queue as powerful as a TM tape. $\endgroup$
    – Hendrik Jan
    Nov 29, 2012 at 22:04
  • $\begingroup$ @HendrikJan What does: "Consider the stack like (bottom) ABCD (top). stack-pop is from top, queue-pop is from bottom (this is directed to myself, I am easily confused). Pushes are from top." mean? $\endgroup$
    – user678392
    Sep 27, 2013 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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