CSE 3502 Syllabus
Fall 2018

Note: this syllabus is subject to change

1. Finite Automata and Regular Languages (7 lectures)
Sipser - chapter 1

Sets, characters, alphabets, strings, languages
definitions and proofs, recursion and induction
regular expressions (REs), regular languages (RLs)
deterministic and nondeterministic Finite Automata
theorems: equivalence of descriptive power for REs/DFAs/NFAs
closure properties of RLs
pumping lemma for RLs

(algorithms for equivalence and minimization of DFAs)
(the LEX tool)

2. Pushdown Automata and Context-Free Languages (6 lectures)
Sipser - chapter 2

context-free grammars (CFGs), context-free languages (CFLs)
derivations: leftmost, rightmost, parse trees
closure properties of CFLs
RLs as a subset of CFLs (two ways to prove it)
Deterministic CFLs
push-down automata (PDAs): regular/string-pushing/simple
Chomsky normal form
theorems: equivalence of PDAs and CFGs
relation between string derivation (leftmost) and parsing (PDA computation)
pumping lemma for CFLs

(intersection of RLs and CFLs)
(CYK parsing)
(BNF grammars)
(the YACC tool)

3. Turing Machines (4 lectures)
Sipser - chapter 3

Turing Machines: ordinary / nondeterministic / multitape
Equivalence of various TM extensions
Deciding vs. recognizing vs. enumerating
Encoding/specification of a TM/PDA/FSA
Simulating other machines, Universal Turing Machine
Church-Turing thesis
(Algorithmic vs. interactive computation)

4. Decidability/Recognizability of problems (5 lectures)
Sipser - chapters 4-5

Decidability of AX, EX, EQX problems
Undecidability of the halting problem
Reducing between problems    
Undecidability of tiling problems, Post systems
(Rice's theorem)

4.  Complexity Theory (4 lectures)
Sipser - chapter 7

Measuring complexity
The classes P and NP
Certificates vs. nondeterminism
NP-complete problems