Why do pushdown automata use a stack?

Question

I'm taking a computer theory class and my professor told us that a pushdown automaton cannot use data structures other than a stack (like a queue or multiple stacks). Why is that?

Answer 1

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 Turing machine. However, the computation power of a push-down automaton is not that much! You can know more about that here.

Answer 2

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 interesting. And apparently it did, because many people (read: the entire field) has agreed to use that definition.
• Why is it interesting? -- See reinierpost's answer.
• Why does my teacher choose to teach PDAs? -- That's a multi-facetted issue; see here for a similar question. The answers carry over.

I'd like to expand on the second bullet a little. How do different definitions come about?

If you take finite control with different memory models, the resulting classes of automata have very different capabilities. In fact, that's a huge part of what automata theory concerns itself with. Once you realize that playing around with definitions can lead to interesting concepts, it's only natural for researchers -- a curious bunch! -- to try and explore the space of possible models.

To list just a few examples of ideas people have had:

• finite memory --> regular
• single stack --> context-free
• single queue --> Turing-complete
• two stacks --> Turing-complete
• infinite tape --> Turing-complete
• heaps --> we don't really know
• monoids --> all kinds of interesting things

And so on and so on.

Note that you can also modify other elements:

• The alphabet -- make it infinite, or continuous.
• The transition function -- make it a relation, or allow $\varepsilon$-transitions.
• The state set -- make it infinite, or allow multiple starting states.
• The inputs -- make them infinite, or trees, or timed sequences.
• Additional restrictions -- use tapes but allow only movement in one direction, or allow to scan k times (alternating directions or always left-right?)

Interesting things can happen!

That's the beauty of mathematical definitions: you usually get something. Then you can spend many months on finding out what it is you got. Maybe it's interesting, maybe not. Maybe it's useful (a dreaded question after talks!), maybe not. But it always is.

Answer 3

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 different properties

At this point you may ask: why does my professor present the pushdown automaton, not some other kind of automaton? What makes the pushdown automaton, with a stack, more interesting than an automaton with some other data structure?

The answer is that non-deterministic pushdown automata can recognize exactly the context-free languages, the languages generated by context-free grammars, which were introduced early on in the history of computer science, in the 1950s, as a technique to describe the syntax of languages: both natural languages, such as English or Russian, and artificial languages, such as programming languages (the first programming language they described was FORTRAN).

This was a big deal at the time. Cybernetics and behaviorism were all the craze. Computers were starting to be applied commercially. One of the areas they were applied to was language processing. How can we describe language?

Well, it consists of utterances (things people say or write down), that consist of sequences of items (words, or sounds). A person who wants to say something will emit those utterances; another person receives them, and makes sense out of them. What if we want to make a computer do the same thing? We will need to find a way to describe a language that can be taught to a computer. We will need a way to generate valid utterances that a computer can use, and a way to recognize those utterances that a computer can use - such that the utterances are actually the utterances of a language humans use, such as English or Russian.

Descriptions of devices that could do such things already existed: there were state machines and various kinds of automata. However, Noam Chomsky, a mathematical linguist at MIT involved in a mechanical translation project, realized state machines aren't powerful enough to describe natural languages such as English, as they cannot describe the phenomenon of recursion in language. He needed something similar, but with the power to describe recursion, and arrived at the context-free grammars, a simple attempt to mathematically formalize rules of grammar as they've been used in describing and teaching languages since at least 500 BC. He proved that these can indeed describe more languages than state machines can, but fewer than some other techniques - a result known as the Chomsky hierarchy. He hoped they would suffice to describe languages such as English and Russian.

Context-free grammars generate utterances. Chomsky thought they basically described how a person generates sentences when speaking. You also need a device to describe how utterances are recognized. That is what pushdown automata are for. They can recognize exactly the utterances generated by a context-free grammar. So they were thought to describe more or less how a human recognizes sentences when listening.

Soon afterwards, it was proved that context-free languages aren't actually capable of describing the syntax of languages completely - you need all kinds of additional machinery to do it properly. This is true both for natural languages and artificial languages. (Context-free languages often tend to be overly ambiguous, while in practice, language can often be disambiguated with all kinds of cues - if these cues are all syntactic, we end up with visibly pushdown languages.)

However, context-free languages and pushdown automata are mathematically very simple and elegant devices, and the Chomsky hierarchy is a simple and elegant result, so they are very useful in education to explain the basics of computer-based language description and recognition (formal language theory). For this reason, they have continued to be a standard part of the theoretical computer science curriculum, and many techniques used in practice are based on them, so they really are requisite knowledge if you want to study anything related to natural language processing, programming language implementation, and other language-related topics.