chapter003 Pushdown Automata and Context Free Languages
section002Pushdown Automata
Our first PDA

Our First Pushdown Automaton

A pusthdown automaton (PDA) , unlike a finite state automaton (FSA), has an unbounded memory, albeit a rather restricted type of unbounded memory: a stack. (So why don't we call such an automaton a "stack automaton?"  Hmmm.   Good point.  They are probably called pushdown automata because in olden days a stack was often referred to as a "pushdown store."  The idea was, one guesses, that as new values were placed on the pushdown store, the ones below were "pushed down" so that only the top value was seen.  The analogy often used to describe a pushdown store was a cafeteria plate dispensor.  Spring-loaded, these devices always make the top plate available for use while hiding the ones below.)

The stack allows PDA's to recognize more complex languages than FSA's.  Here is an example

Example: Recognizing { 0 n 1 n | n≥0} with a PDA

Remember our old friend,

L = { 0 n 1 n | n≥0} ?

This was the first language we tackled in chapter 1 that we discovered could not be recognized by an FSA.  The reason is that every FSA has a fixed, finite number of states for remembering things about the string it is processing.  With a fixed number of states, no FSA can remember now many 0's it has seen in order to match them with the 1's that follow, because the number of 0's and 1's that can occur is unbounded.

However, a PDA can recognize L. One such PDA is illustrated next.  Try this PDA with the following input strings.

  1. ε, the empty string (this just means that you simply run the PDA on an empty input tape.
  2. 0
  3. 1
  4. 01
  5. 0011
  6. Any other strings you desire until you are convinced that this PDA will accept all strings that are in the language L.

(Need help running the PDA? Right click here to open help in new window. )