Peter Linz, An Introduction to Formal Languages and Automata, Sixth Edition
Michael Sipser, Introduction to the Theory of Computation, third edition, Course Technology, 2005
John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman, Introduction to Automata Theory, Languages, and Computation, third edition, Prentice Hall, 2007.
Harry R Lewis and Christos H Papadimitriou, Elements of the Theory of Computation, second edition, Prentice Hall, 1998.
| Class | Topic | Reading | Notebooks and Assignments |
|---|---|---|---|
| 1-2 | Introduction, Mathematical Preliminaries | ||
| 3-5 | DFA, NFA, Equivalence | ||
| 6-7 | Regular grammar, RE | ||
| 8-9 | Pumping Lemma for regular languages | ||
| 10 | DFA Minimization | ||
| 11 | Moore and Mealy Machine, Equivalence | ||
| 12-14 | CFG, Normal Forms, Parsers | ||
| 15-16 | PDA | ||
| 17-19 | CFG Properties, Pumping Lemma | ||
| 20 | DPDA | ||
| 21-23 | Turing machine, Computation | ||
| 24-25 | TM variations | ||
| 26-27 | Universal Turing Machines | ||
| 28-30 | Decidability, Reductions, Regular CF properties | ||
| 31-32 | Undecidability and Reductions | ||
| 33-38 | Time Complexity, NP Completeness, Reductions, Chomsky Heirarchy |