Classes: Tuesdays and Thursdays 9:30-11:00
Books:
Automata and Computability by Dexter C. Kozen
Introduction to Theory of Computation by Michael Sipser
Introduction to Automata Theory, Languages and Computation: Hopcroft, Motwani, Ullman
Grading: Midterm 30%, Assignments/Class tests 10%, Final 60%
Class 01 (Feb 15): Introduction: Few words about theory of computation. Decision Problems, Alphabets, Strings, Operations on Strings [Video][Board work]
Class 02 (Feb 17): Finite automata, regular languages, examples [Video][Board work]
Class 03 (Feb 24): More on DFA: Closure properties, homomorphisms and examples
Class 04 (Mar 01): Nondeterministic finite automata: equivalence with DFA.
Class 05 (Mar 03): NFA: Examples. NFA with epsilon transitions.
Class 06 (Mar 08): NFA with epsilon transitions; Regular expressions
Class 07 (Mar 10): Regular Expressions: Equivalence with DFA, closure properties involving homomorphisms
Class 08 (Mar 15): Non regular languages: Pumping lemma, ultimately periodic sets and unary languages
Class 09 (Mar 17): More examples of non-regular languages, Class test 1
Class 10 (Mar22): Myhill Nerode Relations
Class 11 (Mar 24): Myhill Nerode Theorem
Class 12 (Mar 29): DFA State Minimization
Class 13 (Mar 31): Revision and some problem solving
Class 14 (April 12): Introduction to Context Free Languages: Examples
Class 15 (April 26): Chomsky Normal Form, Pumping Lemma for CFLs
Class 16 (April 28): Push down automata. Equivalence of acceptance by empty stack and final state,
Class 17 ( May 5): Equivalence of PDA and CFG
Class 18 (May 12): Closure properties of CFGs
Class 19 (May 14): Introduction to Turing machines. Recursively enumerable and recursive languages
Class 20 (May 17): Multi-tape TMs, Universal TM, Diagonalization
Class 21 (May 19): Halting Problem, Membership Problem, Many-one Reductions with examples
Class 22 (May 21): Rices Theorems
Class 23 (May 24): Turing Reduction, Arithmetic Hierarchy, Closing of Computability
Class 24 (May 26): Introduction to Complexity theory: DTIME, NTIME, P, NP
Class 25 (May 28): Polytime reductions, NP Completeness, Examples
Class 26(May 31): Review and Ending