Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
3  
You get math.queueexchange.com. –  Asaf Karagila Oct 21 '12 at 10:41
add comment

1 Answer

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|improve this answer
2  
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
add comment

Your Answer

 
discard

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.