CSCI 341 Theory of Computation

Fall 2025, with Schmid

Assignments

Here you can find the PDFs and other materials for various assignments. Remember that everything gets submitted to Gradescope.

Gradescope

Project Specifications

Details about the final project and what it entails can be found below.

Project Specifications
  1. Project Topic Survey (due October 21)
  2. Project Proposal (LaTeX Template), due Nov 3rd
  3. Complete Bibliography (due November 7th)
  4. Draft (due November 21th)
  5. Poster PDF (due December 9th)
  6. Writeup (due December 16th before Final Exam)

Assignment Resources

  1. Salomaa's Axioms, the sheet of rules for doing algebra with regular expressions.

Problem Sets

  1. Problem Set 1: Games, Automata, and Reading Words (LaTeX Source)
  2. Problem Set 2: Language Acceptance, Finite and Infinite Automata, and Finitely Recognizable Languages (LaTeX Source)
  3. Problem Set 3: Determinization, the Structure of \(\mathsf{Fin}\), Regular Expressions, and Antimirov Derivatives (LaTeX Source)
  4. Problem Set 4: Kleene's Theorem and Silent Transitions (LaTeX Source)
  5. Problem Set 5: From Nonregular Languages to Counter Automata (LaTeX Source)
  6. Problem Set 6: Stack Automata (LaTeX Source)
  7. Problem Set 7: Beyond \(\mathsf{CFL}\) and the Nature of Computation (LaTeX Source)
  8. Problem Set 8: Introducing Turing Machines (LaTeX Source)

Workshops

  1. Workshop 1: Induction (LaTeX Source)
  2. Workshop 2: Automata and Regular Expressions (LaTeX Source)
  3. Workshop 3: Nonregular Languages (LaTeX Source)
  4. Workshop 4: Grammars (LaTeX Source)
  5. Workshop 5: Stack Automata (LaTeX Source)
  6. Workshop 6: BuckLang
Top