Theory of Computation (August-November 2015)

References

  1. Introduction to Automata Theory, Languages and Computation (1st edition) by John E. Hopcroft and Jeffrey D. Ullman, Addison-Wesley, 1979.
  2. Introduction to Automata Theory, Languages and Computation (3rd edition) by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Pearson Education, 2007.
  3. Automata and Computability by Dexter Kozen, Springer-Verlag, 1997.
  4. Introduction to the Theory of Computation by Michael Sipser, Thomson Brooks/Cole, 1997.

Homeworks

  1. Homework 1.
  2. Homework 2.
  3. Homework 3.

Lectures

  1. 5 August: Motivation for studying theory of computation, strings, languages, deterministic finite state automata, regular languages. References: Lectures 1-2 of [3] and chapters 0 and 1.1 of [4].
  2. 7 August: examples of designing automata for some languages, closure of regular languages under intersection and union, product construction. References: Lectures 3-4 of [3] and chapter 1.1 of [4].
  3. 12 August: non-deterministic finite state automata. References: chapter 2.3 of [2], lecture 5 of [3] and chapter 1.2 of [4].
  4. 14 August: powerset construction for determinizing non-deterministic automata. References: chapter 2.3 of [2], lecture 6 of [3] and chapter 1.2 of [4].
  5. 19 August: closure of regular languages under concatenation, NFA with ε transitions, regular expressions and their languages. References: chapters 2.5, 3.1 and 3.2 of [2], lectures 8 and 9 of [3] and chapter 1.3 of [4].
  6. 21 August: equivalence of regular expressions and finite state automata, closure of regular languages under homomorphisms. References: chapters 3.1 and 3.2 of [2], lectures 9 and 10 of [3] and chapter 1.3 of [4].
  7. 26 August: pumping lemma for regular languages, Myhill-Nerode relations. References: chapter 4.1 of [2], lectures 11, 12 and 15 of [3] and chapter 1.4 of [4].
  8. 2 September: Myhill-Nerode theorem. Solutions to homework questions. References: lectures 15 and 16 of [3].
  9. 9 September: DFA minimization algorithm. References: chapter 4.4 of [2], lectures 13, 14 of [3] and problem 7.35 of [4].
  10. 11 Septmber: Two-way finite automata. References: lectures 17 and 18 of [3].
  11. 16 Spetember: Context free grammars, derivations, left-most and right-most derivations, parse trees. References: chapters 5.1 and 5.2 of [2], lectures 19 and 20 of [3] and chapter 2.1 of [4].
  12. 18 September: Chomsky Normal Form for context free grammars. References: chapter 7.1 of [2], lecture 21 of [3] and chapter 2.1 of [4].
  13. 30 September: membership problem for context free languages, ambiguity of context free grammars and inherent ambiguity of context free languages. References: chapters 7.4.4 and 5.4 of [2], lectures 26 and 27 of [3] and chapter 2.1 of [4].
  14. 7 October: pumping lemma for context free languages, push down automata, acceptance by final state and acceptance by empty stack. References: chapters 6.1 and 6.2 of [2], lectures 23 and E of [3], chapter 2.2 of [4].
  15. 9 October: equivalence of pushdown automata and context free grammars, deterministic pushdown automata. References: chapters 6.3 and 6.4 of [2], lectures 24, 25 and F of [3] and chapter 2.2 of [4].
  16. 14 October: closure of context free languages under intersection with regular languages, union, concatenation, iteration, homomorphisms and inverse homomorphisms. Non-emptiness problem for context free grammars. References: chapters 7.3 and 7.4 of [2].
  17. 16 October: introduction to Turing machines, multi-tape Turing machines, decidable and recursively enumerable languages. References: chapters 8.1-8.4 of [2], lectures 28-30 of [3] and chapters 3.1-3.2 of [4].
  18. 21 October: non-deterministic Turing machines, simulation by deterministic machines, what happens to the power of Turing machines when restrictions are imposed on the kind of operations it can do? References: chapter 8.4.4 of [2], homework 10 problem 2 of [3] and chapter 3.2 of [4].
  19. 23 October: Simulating a computer by a Turing machine, Church-Turing thesis, universal Turing machines. References: chapter 8.6 of [2], lectures 28 and 31 of [3] and chapters 3.3 and 4.2 of [4].
  20. 28 October: recursively enumerable (r.e.) languages and co-r.e. languages. Proof of the fact that languages that are r.e. and co-r.e. are decidable. References: chapter 9.2 of [2], lectures 28 and 29 of [3] and chapter 3.1 of [4].
  21. 30 October: diagonalization and undecidability of the halting problem for Turing machines. Effective computability and many-one reductions. Undecidability of halting problem for two-stack machines. References: chapters 9.1 and 9.2 of [2], lectures 31, 32 and 33 of [3] and chapters 4.2 and 5.1 of [4].
  22. 4 November: Rice's theorem. References: chapter 9.3 of [2], lecture 34 of [3] and problem 5.22 of [4].
  23. 11 November: Enumerating machines, counter machines. References: lecture 30 of [3] and chapter 3.2 of [4].
  24. 18 November: Undecidability of Post's correspondence problem and undecidability of some problems related to context free languages. References: chapters 9.4 and 9.5 of [2], lecture 35 of [3] and chapters 5.1 and 5.2 of [4].
  25. 20 November: Tiling problem and its variants. Reference: http://www.cs.bc.edu/~straubin/cs385-07/tiling.