Automata, Logic, and Computation (CS 422)


Instructor:


Course material on Canvas
Please do not use Canvas to contact me. Use my email, and prefix the subject line with "CS422:".


Course Description:



Textbook (required):




Weekly Schedule (tentative)

Week Topics Assigned reading Homework
8/23-8/27 Introduction, DFAs, NFAs, closure properties Chapter 0, Chapter 1 (till page 54) Homework 0, Homework 1
8/30-9/03 NFAs, determinization: subset construction, closure properties Chapter 1 till page 66 Homework 2
9/06-9/10 Regular expressions, Non-regular languages Chapter 1, till Section 1.3 Homework 3
9/13-9/17 Pumping lemma and non-regular languages, Myhill-Nerode theorem Chapter 1 Homework 4
9/20-9/24 Characterizing non-regular languages, DFA minimization, Context-free grammars Section 2.1 Homework 5 (optional)
9/27-10/01 Pushdown automata, review Section 2.2 Midterm prep
10/04-10/08 Midterm 1, PDA-CFG equivalence Section 2.2 Homework 6
10/11-10/15 Midterm 1 solutions, pumping lemma for CFLs, CYK algorithm Section 2.3
10/18-10/22 Turing machines, non-determinism Chapter 3 Homework 7
10/25-10/29 Decidability, Reducibility Chapter 4, Section 5.1 Homework 8
11/01-11/05 Reducibility Sections 5.1, 5.3, 6.3
11/08-11/12 Reducibility, Review Midterm preparation
11/15-11/19 Midterm 2, Reducibility Homework 9
11/29-12/03 First-order logic Section 6.2, notes Homework 10
12/06-12/10 Midterm 2 solutions, review
12/13-12/17 Final exam



Lectures:



Prerequisites:



Grading:

The course grade will be based on the following elements (minor adjustments to the weights may be made).

Homework and Readings: