1. Finite Automata and Regular Languages (8 lectures)
Sipser - chapter 1
alphabets, strings, languages
inductive/recursive definitions
regular expressions (REs), regular languages (RLs)
deterministic and nondeterministic Finite Automata (DFAs/NFAs)
3 automata representations: formal (set-based), table-based, diagram
theorems: equivalence of descriptive power for REs/DFAs/NFAs
proof by structural induction
conversions: from RE to NFA, from NFA to DFA
closure properties of RLs
pumping lemma for RLs(minimization of DFAs)
(the LEX tool)
(algorithm for determinining if w is in L(DFA), if L(DFA) is empty)
(algorithm for deciding whether L(DFA1) = L(DFA2))
2. Pushdown Automata and Context-Free Languages (6 lectures)
Sipser - chapter 2
context-free grammars (CFGs), context-free languages (CFLs)
parse trees, ambiguity: ambiguous grammar vs. inherently ambiguous language
derivations: leftmost, rightmost
closure properties of CFLs
RLs as a subset of CFLs (two ways to prove it)
normal forms: CNF/DNF for boolean expressions, BNF for grammars
Chomsky normal form -- converting CFG to CFG in Chomsky normal form
push-down automata (PDAs)
regular/string-pushing/simple PDAs -- converting between them
equivalence of PDAs and CFGs; converting CFG to PDA and vice versa
relation between string derivation (leftmost) and shift-reduce parsing (PDA computation)
pumping lemma for CFLs(CYK parsing)
(the YACC tool)
(algorithm for determinining if w is in L(CFG), if L(CFG) is empty)
3. Turing Machines (5 lectures)
Sipser - chapter 3
Turing Machines: ordinary / nondeterministic / multitape / non-moving
Equivalence of various TM extensions
Deciding vs. recognizing vs. enumerating vs. computing functions
Enumerable languages = recognizable languages
Enumerable in order languages = decidable languages
Encoding/specification of a TM/PDA/FSA
Simulating other machines, Universal Turing Machine
Turing thesis, erroneous strong Turing thesis(Algorithmic vs. interactive computation)
4. Decidability/Recognizability of problems (5 lectures)
Sipser - chapters 4-5
Decideable languages = intersection (recognizable, co-recognizable languages); have decidable complements
Decidability of AX, EX, EQX
Recognizability, undecidability of of ATM
Reducing between problems
Undecidability ETM, the halting problem
Unrecognizability of EQTM and its complement
Undecidability of the Post Correspondence Problem (use of computation histories)
Rice's theorem(diagonalization)
(mapping reducibility)
(linear bounded automata)
5. Complexity Theory (4 lectures)
Sipser - chapter 7
Measuring time complexity for deterministic and non-deterministic TMs
Polynomial equivalence of deterministic Turing-complete models of computation
Correspondence between YES/NO problems and decideable languages
The classes P and NP of problems (languages)
Defining NP: Certificates vs. nondeterminism
Polynomial-time reducibility
NP-complete problems