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.
In a DFA, the tape is read only, the head moves to the right only. DFAs are limited in power. They recognize regular languages but cannot recognize many other 'simple' languages like $a^nb^n$
- a
- a
- a
- a
- b
- b
7.1.2. Transitions Types for PDAs¶
Similar to a NFA, PDAs can have different behaviors on the same input. That is, an NFA can have multiple choices about what to do on the input symbol 'a'. This is the fundamental concept of non-determinism. In a similar way, a PDA can choose between multiple behaviors on a given input condition (current state, current input, and current top of the stack). A PDA that has multiple behaviors on a given input is called a Non-deterministic PDA (NPDA).