# Theory of Computation (Automata, Computability, and Complexity)

## IMPORTANT MESSAGES:

- We are back to classroom teaching/learning, although part of the lectures will still be provided remotely
- Each week, slides and/or videos will be uploaded
- Grading will be based on three (3) quiz and one (1) final exam

## Learning Objectives:

*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: cai@omu.ac.jp
- Office hour: anytime appointment by email

## Lecture Schedule:

- Period: Sep. 2022 -- Feb. 2023
- Day and Time: Tuesdays 15:00-16:30

## Textbook / Reference:

There is no textbook. Lecture notes will cover all contents. Two excellent references are:

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

## Prerequisites:

None

## Course Outline:

` Dates Topics`

- 2022.09.27 Introduction, finite automata
- 2022.10.04 Strings, languages
- 2022.10.11 Nondeterministic finite automata
- 2022.10.18 Regular operations, regular expressions
- 2022.10.25 Tutorial 1
- 2022.11.08 Quiz 1, nonregular languages, pumping lemma
- 2022.11.15 Context-free grammars, context-free languages, pushdown automata
- 2022.11.22 Non-context-free languages, pumping lemma
- 2022.11.29 Turing machines
- 2022.12.06 Turing-recognizable languages, Turing-decidable languages, variants of Turing machines
- 2022.12.13 Tutorial 2
- 2022.12.20 Quiz 2, Algorithms, decidable problems, undecidability
- 2023.01.10 Time complexity, P and NP
- 2023.01.17 Tutorial 3
- 2023.01.24 Quiz 3, NP completeness
- 2023.01.31 Exam, NP complete languages