7.1. Pushdown automaton¶
7.1.1. PDA: Pushdown Automata¶
One of defining characteristics of DFAs and NFAs is that they have no memory. So there is no history or way to store information aside from what state they are currently in. In this and future chapters, we will study two types of machine with memory: The Pushdown Automata (or PDA, so-called because it has a stack) and the Turing Machine (that has a somewhat more flexible form of memory). Not coincidentally, we will find that these machines have more capability than do DFAs in terms of the languages that they can recognize.
