CSCI 341 Theory of Computation

Prof. Schmid is an automata theorist by trade. This sequence of notes is partly based on their notes on the topic, especially the contents of Part I of the course. The latter half of the notes is in part based on earlier iterations of the course taught by Prof. Talmage.

• What is computation?
• Section 1. Automata and Languages
  1. Puzzle games, solutions, and state diagrams
  2. Automata
  3. Reading words
  4. Languages and acceptance
  5. Finite and infinite automata
  6. Finitely Recognizable Languages
  7. Determinization
  8. The Structure of \(\mathsf{Fin}\)
  9. Regular Expressions
  10. Antimirov Derivatives
  11. The Algebra of Regular Languages
  12. Kleene's Theorem
  (read below at own risk)
  13. Silent Transitions
• Section 2. Parsing and Checking Context-free Languages
• Section 3. Decidability and Undecidability
• Section 4. Complexity
• Concluding Remarks and Open Problems