SUNY Geneseo Department of Mathematics

Every PDA has a CFG

Friday, February 26

Math 304
Spring 2016
Prof. Doug Baldwin

Misc
- Colloquium
  - “The Eigenvalue Machine”
  - Dr. Kristopher Lee, Iowa State
  - Tuesday, March 1, 4:00 PM, Newton 214
  - Extra credit for write-ups
Questions?
- What do variables in this CFG represent?
  $A_{pq} is strings read from input while PDA goes from q to p with no net change to stack$
Equivalence of PDAs and CFGs, Part 2
- Lemma 2.27
- Example
  - Mostly the final grammar
  - But starting looking at where that grammar comes from
Next
- Non-context-free languages
- Read section 2.3