7.1. Pushdown Automata¶
7.1.1. PDA: Pushdown Automata¶
A significant characteristic of DFAs and NFAs is that they have no memory. So there is no history or way to store information aside from the state that they are currently in. This restricts what languages they can recognize.
Consider what adding the ability to make use of just a single counter variable can do. For example, it is easy to recognize the language of balanced parentheses with a counter. Simply increment the counter when a left parenthesis is seen, and decrement when a right parenthesis is seen. If the counter ever goes negative, then reject. If it is zero after processing the string then accept, otherwise reject. Likewise, a counter will allow recognizing the language comprised of strings of the form \(a^nb^n\).
But another alternative to storing a counter is to use a stack. Balanced parentheses can be recognized by pushing left parentheses onto the stack, and popping the top of the stack when encountering a right parentheses. Strings of the form \(a^nb^n\) can likewise be recognized by pushing the initial a’s onto the stack, and then popping them off as the b’s are processed. Using a stack gives all of the capabilities of a counter, with a bit more flexibility.
In the next few chapters we will study two types of machine with memory. The Pushdown Automata (PDA) uses a stack for its memory, and we will see that this allows it to recognize a wider range of languages than can the DFA or NFA. The Turing Machine has a more flexible form of memory than does the PDA, which will allow it to recognize an even broader range of languages.
7.1.6. Something to Think About¶
The PDA with its stack can easily recognize the language comprised of strings of the form \(a^nb^n\). Can it also recognize the language comprised of strings of the form \(a^nb^nc^n\)?
Can the PDA recognize the language $wcw^R$? That is the language with a string $w$ followed by the symbol $c$ followed by the reverse of $w$. Certainly it can, but can it do this deterministically?
Can the PDA recognize the language $ww^R$? Yes, but can it do this deterministically?
