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?

up vote 11 down vote accepted

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.

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:

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.

  • Your table notes that pushdown automata allow some tasks that finite state machines cannot perform to be done without needing a Turning machine, but fails to note the significance: given a program for any simpler-than-Turing machine along with some input, it will be possible to determine within a finite time whether the program could ever run to completion when given that input. Once a task becomes complicated enough to require a Turing machine, decidability is no longer a given. – supercat Oct 24 at 20:53
  • @supercat That seems completely irrelevant to the question, and I'm not even sure it's true. I'm fairly certain that there are sub-Turing-complete models of computation with undecidable halting problem! – Raphael Oct 24 at 22:56
  • @supercat: You always get that decidability if you limit the amount of possible configurations to a finite set, which are most formal definitions of automata (finite set of states, finite alphabet, finite input). – hoffmale Oct 24 at 23:10
  • @hoffmale How is that relevant? PDAs already have infinitely many configurations -- even for a fixed input, if you allow $\varepsilon$-transitions! -- but their halting problem is trivial. – Raphael Oct 25 at 8:33
  • @Raphael: I read the real essence of the question as "why is there a recognized category of automata whose behavior is defined in terms of a stack", rather than "why does the category of automata that is defined in terms of a stack, use a stack". PDAs are the only common category of automata I'm aware of which are (1) easily described, (2) can decide a wider range of problems that finite state machines, and (3) are 100% decidable within finite time. There are more powerful categories of 100% decidable automata, but they're harder to describe and aren't used as much. – supercat Oct 25 at 15:23

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 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 computer 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), 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 transition 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. 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 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 basically how a human recognizes sentences when listening.

Soon afterwards, it was discovered 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. (To be honest, I think Chomsky meant to come up with visibly pushdown languages, except he didn't realize the difference, and if he had, it would have saved us all a lot of hassle.)

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.

  • 4
    I think that's the first time I've heard of Noam Chomsky referred to as a mathematician. While there is certainly some fuzziness between linguistics, computer science, and mathematics, I think it would be more accurate to call him a linguist. – 8bittree Oct 24 at 16:18
  • 1
    Indeed, his Wikipedia page explains he was a linguist specializing in mathematical linguistics. I've changed it. Thanks! – reinierpost Oct 25 at 14:46

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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