# Automata, Formal Languages, and Computational Complexity (Fall 2021)

In your journey through computation, you likely have noticed that many problems can be solved with the same solution through a skill you have honed called abstraction. Through this process, you may have noticed more nuanced connections between problems. Some problems require some translation before being solved using the solution to another problem. Other problems are immune this sort of transformation and feel fundamentally more difficult than others. Some problems feel downright impossible to solve—are they actually impossible?

In this course, we study the theory of computation where we use mathematics to model problems of increasing complexity and study their relationships with each other. By going through this modeling process, we can:

• Deeply understand a problem and its potential corner cases.
• Prove properties of a problem, e.g., the correctness a candidate solutions.
• Reduce a problem to another problem, i.e, formally solve one problem in terms of another.
• Categorize a problem as easier or harder than other problems in a precise way.

By the end of the course, we will explore the limits of computation. Are there problems that are intractable in practice? Are there problems that can provably never have a solution?

## Schedule

F 08/27 Introductions
Week 1: Preliminaries
M 08/30 Review of Mathematical Literacy Interpreting Definitions
W 09/01 Constructive and Classical Proof Formal Proof
F 09/03 Deterministic Finite Automata DFA Basics
Week 2: Finite Automata
M 09/06 Design with Finite Automata DFA Design
W 09/08 Nondeterminism Exploring Nondeterminism
F 09/10 Equivalence of Models Finding Essence
Week 3: Regularity
M 09/13 Closure Properties Closure Problems
W 09/15 Regular Expressions Regular Expressions
• Demo #1 revisions due
F 09/17 Analysis of Regular Models Exploring the Regular Models
Week 4: Beyond Regularity
M 09/20 Irregularity and the Pumping Lemma Irregularity
W 09/22 Myhill-Nerode Theorem Applying Myhill-Nerode
• Demo #2 revisions due
F 09/24 Context-Free Grammars Context-free Grammars
Week 5: Turing Machines
M 09/27 Introduction to Turing Machines Introduction to Turing Machines
• Demo #4 due
W 09/29 Variants and The Church-Turing Thesis Properties and Variants of TMs
• Demo #3 revisions due
F 10/01 (No class, LA day!)
• LA #1 out
Week 6: Time Complexity
M 10/04 Time Complexity Time Complexity
W 10/06 NP-Completeness NP-Completeness
• Demo #4 revisions due
F 10/08 The Cook-Levine Theorem The Cook-Levine Theorem
Week 7: NP-Completeness
M 10/11 Mapping Reducibility Mapping Reducibility
• Exploration #1 out
• Demo #5 due
W 10/13 Classical NP-Complete Problems More Mapping Reductions
F 10/15 P vs. NP
(Fall break: 10/18 to 10/22)
Week 8: Space Complexity
M 10/25 Space Complexity Space Complexity
W 10/27 Savitchs Theorem Space Relationships
• Demo #5 revisions due
F 10/29 PSPACE and PSPACE-Completeness PSPACE-Completeness
Week 9: Complexity Wrap-Up
M 11/01 Sublinear Space Complexity Complements and Complexity
• Demo #6 due
W 11/03 Hierarchy Theorems Complexity Wrap-Up
F 11/05 (No class, LA day!)
• LA #2 out
Week 10: Computability
M 11/08 Machine Analysis Machine Analysis
W 11/10 Diagonalization Diagonalization
• Demo #6 revisions due
F 11/12 Undecidability Undecidability
Week 11: Undecidability
M 11/15 Undecidability Reductions Machine Behavior Undecidability
W 11/17 The Post-Correspondence Problem PCP
F 11/19 Rices Theorem Rices Theorem
Week 12: Computability and Logic
M 11/22 Recursion and Logical Theories Quine Exploration
• Demo #8 due
W 11/24 (No class, pre-Thanksgiving Break!)
• Demo #7 revisions due
(Thanksgiving Break: 11/25 and 11/26)
Week 13: Approximation and Probabilistic Computation
M 11/29 Approximate Computing PTASs
W 12/01 Approximation with Linear Programming Approximation with Linear Programming
• Demo #8 revisions due
F 12/03 Hardness of Approximation Hardness of Approximation
Week 14: The Future of Computation
M 12/06 Solving SAT Efficiently DPLL
• Demo #9 due
W 12/08 The Theory of Computation
F 12/10 (No class, LA day!)
• LA #3 out
Finals Week
M 12/13
T 12/14
• LA #4 out
W 12/15
• Demo #9 revisions due
F 12/17
• All remaining work due

## Learning Goals

• Learning Assessment 1
• Represent a problem using a regular model of computation.
• Prove closure and algorithmic properties of the regular languages.
• Prove the irregularity of a problem.
• Represent a problem using a context-free model of computation.
• Represent a problem using a Turing machine.
• Prove closure and algorithmic properties of Turing machines.
• Learning Assessment 2
• 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 the P vs. NP problem.
• Prove that a problem is in a particular space complexity class.
• Describe the essential charactistics of problems belonging to each of the major complexity classes.
• Describe the practical relationships between various time and space complexity classes.
• Learning Assessment 3
• Prove the decidability of a given machine analysis algorithm.
• Prove the undecidability of a given problem by way of a reduction.
• Prove the undecidability of a given problem through Rice's Theorem.
• Describe the practical ramifications of computational undecidability.
• Describe practical problem solving strategies for dealing with intractable problems.
• Design and reason about an approximation algorithm to an optimization problem.