- How does a PDA compute?
- Section 2.2 through “Examples of Pushdown Automata”
- Description of pushdown automata
- Formal definition
- Nondeterministic and deterministic PDAs not the same
- NPDAs have same power as context free grammars (proof coming)
- More examples
- Balanced parentheses
- A regular language: ab*a
- Every regular language can be recognized by a PDA that doesn’t use its stack
- Therefore regular languages are a subset of what PDAs can recognize
- Every regular language can be recognized by a PDA that doesn’t use its stack
- Postfix expressions (as usual, with 1-digit operands and +, * operators)
- With the dummy 0 this pushes when reading an operator replaced with the actual value of the operation, this is basically the algorithm real programs use to evaluate postfix
- Balanced parentheses
- Problem set
- Pushdown automata are equivalent to context free grammars, part 1
- Read “Equivalence with Context-Free Grammars” through proof of
Lemma 2.21
- Page 117 through 120