CSCI 341 Theory of Computation

Fall 2025, with Schmid

Table of Contents

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.

  1. What is computation?
  2. 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
    13. Silent Transitions
  3. Beyond Regularity
    1. Pumping Lengths
    2. Polynomial Systems and Grammars
    3. Parse Trees
    4. Adding Expressive Power to Automata
    5. Stack Automata
      6. (read below at own risk)
    6. CFL = Stack
  4. Decidability and Undecidability
  5. Complexity
  6. Concluding Remarks and Open Problems
Top