CSC 341 – Automata, Formal Languages, and Computational Complexity (Fall 2022)

Instructor: Dawn Nye
Office Hours: MWF 4:00 PM – 5:00 PM (or by request/whenever my door is open)
Mentor: Moiz Yousufi
Mentor Sessions: TBD
Meeting Times: MWF 1:00 PM – 1:50 PM (Science 3820)
Textbook: Introduction to the Theory of Computation (3rd Edition) by Michael Sipser

Computer science is as much concerned with the analysis of computation as it is with implementation. In the study of algorithms, for example, we frequently analyze best, worst, and (when appropriate) average and amortized case runtimes. We might instead analyze the space requirements of an algorithm. For example, most sorting algorithms can be done in place requiring no more than linear space. Reachability (roughly speaking finding a path) can be done in as little as log space. Pursuing a formalization of these notions allows us to argue about the relative difficulty/tractability of problems or to determine if they are impossible outright.

In this course, we study the theory of computation to formally model problems and study their relationships with one another. In doing so, we can gain insight into not just a problem but all related problems. We can also identify problems which are intractable and might require probabilistic or approximation algorithms to solve with reasonable resources. Some problems, we will discover, can provably never have a solution, a fact which an imprecise understanding can often obscure.

---

Schedule

Date	Topic*	Reading†	Assignments
8/26	Introductions
8/29	Proofs	Chapter 0
8/31	Proofs
9/2	Formal Languages Deterministic Finite Automata	Section 1.1	HW1
9/5	Nondeterminism	Section 1.2
9/7	DFA and NFA Equivalence
9/9	Closure Properties		HW2 HW1 Due
9/12	Regular Expressions	Section 1.3
9/14	Decidable Properties
9/16	Irregular Languages	Section 1.4	HW3 HW2 Due HW1 Resubmission Due
9/19	Myhill-Nerode Theorem	Problems 1.51 and 1.52
9/21	Kolmogorov Complexity	A New Approach to Formal Language Theory by Kolmogorov Complexity (via ProQuest Central) [Suggested] Section 6.4 [for the ambitious]
9/23	Context-Free and Context Sensitive Languages	Chapter 2 [Suggested]	Exam 1
9/26	Turing Machines	Section 3.1	HW3 Due
9/28	Variants, Other Models, and the Church-Turing Thesis	Sections 3.2 and 3.3
9/30	Decidability	Section 4.1	HW4 HW2 Resubmission Due
10/3	Diagonalization	Section 4.2	Exam 1 Due
10/5	Undecidability	Sections 5.1
10/7	Rice’s Theorem	Problem 5.28	HW5 HW4 Due
10/10	Reducibility & Reductions	Section 5.3
10/12	The Post-Correspondence Problem	Section 5.2	HW3 Resubmission Due
10/14	Oracles & The Arithmetic Hierarchy	Section 6.3	HW5 Due
Fall Break
10/24	Asymptotics	Section 7.1	HW 6
10/26	P	Section 7.2
10/28	NP	Section 7.3
10/31	Graph Notes NP-Complete	Section 7.4	HW7 HW6 Due
11/2	NP vs co-NP
11/4		Section 7.5
11/7			Exam 2 HW7 Due HW4 Resubmission Due
11/9	Space Complexity	Section Introduction
10/10			HW5 Resubmission Due
11/11	Savitch’s Theorem	Section 8.1
11/14	PSPACE		HW8 Exam 2 Due
11/16	L and NL
11/18	NL Continued
11/21	Space-Time Hierarchy	Section 9.1 [Suggested Skim]	HW9 HW8 Due
11/23	Circuit Complexity	Section 9.3
Approximately Thanksgiving
11/28	The Time-Circuit Link		HW10 HW9 Due HW6 Resubmission Due
11/30	The Cook-Levine Theorem Revisited
12/2	AC and NC
12/5	P/Poly		Exam 3 HW10 Due
12/7	Probabilistic Algorithms
12/9	Approximation Algorithms		HW7 Resubmission Due HW8 Resubmission Due HW9 Resubmission Due
12/14			Exam 3 Due HW10 Resubmission Due

* Subject material on any given day may drift forward or back according to actual progress during class
† Supplemental readings beyond the scope of the textbook may appear at future dates

---

Learning Outcomes

• Formal Automata and Languages
  • Represent a problem using finite automata
    • Deterministic and non-deterministic finite automata
    • Regular languages
    • Equivalence of NFAs and DFAs
  • Prove closure and algorithmic properties of the regular languages
  • Prove the irregularity of a problem
    • Pumping Lemma
    • Kolmogorov approach
    • Myhill-Nerode Theorem
  • Represent a problem using a context-free model of computation
    • Stack machines
    • CF grammars
  • Prove a language is not context-free
  • Represent a problem using a context-sensitive model of computation
    • Linear bounded automata
    • CS grammars
  • Represent a problem using a Turing machine
  • Prove closure and algorithmic properties of Turing machines
• Computability Theory
  • Prove the decidability of a problem
    • Prove the decidability of a problem via an explicit construction
    • Prove the undecidability of a problem via a reduction
    • Prove the undecidability of a problem via Rice’s Theorem
  • Prove that a problem is recognizable, co-recognizable, or neither
  • Describe the practical ramifications of computational undecidability
    • Summarize the Church-Turing Hypothesis and Gödel’s Incompleteness Theorems
• Computational Complexity
  • Prove that a problem is in a particular time complexity class
  • Prove that a problem is NP-complete by way of a reduction
  • Explain the practical ramifications of P vs NP
  • Describe practical problem-solving strategies for dealing with intractable problems
    • Approximation algorithms
    • Probabilistic algorithms
• As Time Permits
  • Prove that a problem is in a particular space complexity class
    • Formally define each of the major complexity classes
    • Describe the essential characteristics of a problem belonging to each complexity class
    • Describe the practical relationships between various time/space complexity classes
  • Prove that a problem is in a particular circuit complexity
  • Understand and utilize oracle machines for higher levels of computation
  • Understand other models of computation and be able to generate new ones