# Tag Info

### Why do pushdown automata use a stack?

There are several possible layers to your question. Why must PDAs have a stack? -- By definition! That's just how it is. But why are they defined like that? -- Somebody thought it might turn out ...
• 72.6k

### Why do pushdown automata use a stack?

OmG and Raphael have already answered your question: pushdown automata use a stack because they're defined that way if they didn't use a stack, what you'd get is a different type of automaton, with ...
• 5,736
Accepted

### Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form

Sipser clearly implies an or between those two rules. The two definitions say the same thing. Meanwhile, in formal language theory, it is quite common for two textbooks or article to not say the same ...
• 5,736
Accepted

### Why do pushdown automata use a stack?

If you change the stack to the queue or multiple stacks, the power of computation will be increased! (as you know, we can model a queue with two stacks). If we use a queue, it can be powerful as a ...
• 3,572
Accepted

### Is {a^n (a+b)^n | n>0} a Deterministic CFL?

You needn't determine the end of "first part". Note $L$ is exactly the set of strings satisfying the following three constraints: Its length is even. It only contains $a$ and $b$. The first $b$ ...
• 7,520
Accepted

• 30.7k

### Can you pop 2 elements at a time in a PDA

In order to find the answer, one must consult the definition of a pushdown automaton. In general, one should always go back to the definitions when in doubt. According to the definition in Sipser's ...
• 2,516