Adding a Stack to Finite Automata

Since there are some languages that are not regular, we’ll now look at a type of machine that accepts some of these languages. The type of machine we’ll use is essentially identical to the finite automata, except that we add the use of an external stack data structure as auxiliary storage, and it is aptly named a pushdown automaton (PDA). The class of languages pushdown automata accept are the context-free languages (CFLs). We’ll also see that, unlike regular languages, there is a difference between nondeterministic and deterministic CFLs. Some CFLs are inherently nondeterministic.

Adding a stack to finite automata

With a stack at our disposal, we have the option of popping and/or pushing symbols from/onto the stack as we process an input stream. Transitions are taken depending on the current state, the symbol read, and the symbol on the top of the stack. When following a transition, we can not only change state but we can also pop one symbol and push one or more symbols onto the stack. Transition edges in PDAs take the form <read-char>,<pop-char> $\rightarrow$ <push-string>. The following figure shows a PDA that accepts the language $L = \{a^nb^n\;|\;n>0\}$.

We always start with an empty stack. The idea with the PDA above is to add an $X$ to the top of the stack as a counter every time we read an $a$. Whenever we read a $b$, the applicable transition indicates that we must pop an $X$ from the stack. The PDA accepts only if it ends in an accepting state and the stack is empty.

The transition rule $a, \lambda \rightarrow X$ means, “If an $a$ is read from the input stream, don’t pop anything from the stack and push an $X$ onto the stack.”

Note: We use the right-arrow because in general, we are replacing a symbol on the top of the stack with whatever symbols we are pushing, like the replacement rules in grammars, which also use right-arrows. If you find arrows tedious to draw by hand, you can use a slash, as in $b,X/\lambda$, or just a comma: $b,X,\lambda$.

The presence of a lambda means to ignore reading, pushing, or popping, depending on where it appears in the transition rule. The symbol before the arrow represents the symbol to pop, and the string after the arrow represents the string of symbols to push. If the expected symbol is not present to be popped, then that transition rule cannot be applied. If there is no applicable rule, the machine “crashes” (similar to going to a jail state) and rejects the input. We rarely include jail states in PDAs.

Remember: Processing a string in a PDA must end in an accepting state with an empty stack to accept an input string. At most, one symbol at a time may be popped from the stack.

The following table traces the processing of the input string $aabb$ through the PDA in the figure above.