CS 301: Languages and Automata

DateTopic and reading
Week 1
Mon, Jan 15No class: MLK Day
No reading
Wed, Jan 17Introduction: Preliminaries [slides]
Reading
  • Sipser 0.
Week 2
Mon, Jan 22Deterministic finite automata (DFAs) [slides]
Reading
  • Sipser 1.1.
Wed, Jan 24Nondeterministic finite automata (NFAs) [slides]
Reading
  • Sipser 1.2.
Week 3
Mon, Jan 29Regular expressions (regex) [slides]
Reading
  • Sipser 1.3.
Wed, Jan 31DFAs, NFAs, and regex [slides]
No reading
Week 4
Mon, Feb 05Nonregular languages and the pumping lemma [slides]
Reading
  • Sipser 1.4.
Wed, Feb 07Closure properties of regular languages [slides]
No reading
Week 5
Mon, Feb 12Regular languages recap [slides]
No reading
Wed, Feb 14Context-free grammars (CFGs) [slides]
Reading
  • Sipser 2.1.
Week 6
Mon, Feb 19Chomsky normal form (CNF) [slides]
No reading
Wed, Feb 21Exam 1 Review [slides]
No reading
Week 7
Mon, Feb 26Chomsky normal form (CNF)
No reading
Wed, Feb 28Pushdown automata (PDAs) [slides]
Reading
  • Sipser 2.2.
Week 8
Mon, Mar 05Closure properties of context-free languages [slides]
No reading
Wed, Mar 07Non-context-free languages and the pumping lemma [slides]
Reading
  • Sipser 2.3.
Week 9
Mon, Mar 12Turing machines (TMs) [slides]
Reading
  • Sipser 3.1.
Wed, Mar 14Turing machines (TMs) [slides]
Reading
  • Sipser 3.2.
Week 10
Mon, Mar 19Church-Turing Thesis and Decidability [slides]
Reading
  • Sipser 3.3, 4.1.
Wed, Mar 21Class canceled
No reading
Week 11
Mon, Mar 26No class: Spring break
No reading
Wed, Mar 28No class: Spring break
No reading
Week 12
Mon, Apr 02Decidability [slides]
Reading
  • Sipser 4.1.
Wed, Apr 04Undecidability [slides]
Reading
  • Sipser 4.2.
Week 13
Mon, Apr 09Undecidability and reducibility [slides]
Reading
  • Sipser 5.1.
Wed, Apr 11Exam review [slides]
No reading
Week 14
Mon, Apr 16Class canceled
No reading
Wed, Apr 18Mapping reducibility [slides]
Reading
  • Sipser 5.3.
Week 15
Mon, Apr 23Time complexity and P [slides]
Reading
  • Sipser 7.1, 7.2.
Wed, Apr 25P and NP [slides]
Reading
  • Sipser 7.3.
Week 16
Mon, Apr 30NP-completeness [slides]
Reading
  • Sipser 7.4.
Wed, May 02Final exam review [slides]
No reading