Theory of Computation (Automata, Computability, and Complexity)

  • Study mathematical models of computation: automata, Turing machines;
  • learn the limit of computation: computability theory;
  • analyze the efficiency of computation: complexity theory.

Instructor:

  • Prof. Kai Cai (Engineering Building F-610)
  • Email: kai.cai@eng.osaka-cu.ac.jp
  • Office hour: after each lecture or by email appointment

Lecture Schedule:

  • Period: Oct. 2019 -- Feb. 2020
  • Day and Time: Tuesdays 15:15-16:55
  • Location: Engineering Building B-113

Textbook / Reference:

Lecture notes in class will cover all contents. Two excellent references are:

  1. M. Sipser, "Introduction to the Theory of Computation", Course Technology, 2013. (Available in our library; there is Japanese translation for this book.)
  2. J.E. Hopcroft, R. Motwani, J.D. Ullman, "Introduction to Automata Theory, Languages, and Computation", Addison Wesley, 2006. (Available in our library)

Prerequisites:

None

Grading:

  • Final test 100% (2020.02.04)

Homework Assigments:

(Submission of homework is not mandatory; only submitted homework will be marked)

Course Outline (tentative):

    Dates              Topics
  1. 2019.10.01 Introduction (slides.pdf) (slides.pptx)
  2. 2019.10.08 Finite automata (slides.pdf) (slides.pptx)
  3. 2019.10.15 Regular languages (slides.pdf) (slides.pptx)
  4. 2019.10.29 Nondeterministic finite automata, regular operations (slides.pdf) (slides.pptx)
  5. 2019.11.05 Regular expressions (slides.pdf) (slides.pptx)
  6. 2019.11.12 Nonregular languages, pumping lemma (slides.pdf) (slides.pptx)
  7. 2019.11.19 Context-free grammars, context-free languages, pushdown automata (slides.pdf) (slides.pptx)
  8. 2019.11.26 Non-context-free languages, pumping lemma (slides.pdf) (slides.pptx)
  9. 2019.12.03 Turing machines (slides.pdf) (slides.pptx)
  10. 2019.12.17 Turing-recognizable languages, Turing-decidable languages, variants of Turing machines (slides.pdf) (slides.pptx)
  11. 2020.01.07 Algorithms, decidable problems, decidability (slides.pdf) (slides.pptx)
  12. 2020.01.14 Undecidable problems (slides.pdf) (slides.pptx)
  13. 2020.01.21 Time complexity, P and NP (slides.pdf) (slides.pptx)
  14. 2020.01.28 Summary (slides.pptx)
  15. 2020.02.04 Final test
  • For 2018 course see here.