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\}$.