SUNY Geneseo Department of Mathematics

Exercises and Such

Math 304
Spring 2016
Prof. Doug Baldwin

Last modified April 26, 2016

These are the assignment handouts and similar material from Math 304 (Theory of Computability). Send comments, questions, etc. related to these documents to Doug Baldwin.

  1. Problem Set 1—Finite Automata
  2. Problem Set 2—Regular Expressions
  3. Problem Set 3—Non-Regular Languages
  4. Problem Set 4—Context Free Grammars and Pushdown Automata
  5. Problem Set 5—Proofs about Context Free Languages
  6. Discussion—History of Finite Automata
  7. Problem Set 6—Turing Machines and Algorithms
  8. Exam 2 Solution
  9. Problem Set 7—Undecidability
  10. Optional Presentations—Unsolvable Problems
  11. Problem Set 8—Undecidability by Reduction
  12. Problem Set 9—Computation Histories and Reduction
  13. Problem Set 10—Lambda Calculus