Theory of Computation (Automata, Computability, and Complexity)

IMPORTANT MESSAGES:

Due to COVID-19, all lectures will be given remotely
Each week, slides and videos will be uploaded
Grading will be based on 5 homework assignments (please see "Homework" section below for submission deadlines)

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: kai.cai@eng.osaka-cu.ac.jp
Office hour: by email

Lecture Schedule:

Period: Oct. 2020 -- Feb. 2021
Day and Time: Tuesdays 15:15-16:55

Textbook / Reference:

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

Homework Assigments:

Course Outline:

    Dates              Topics

2020.10.06 Introduction, finite automata
- (Lecture1-1_introduction.pptx) (Lecture1-1_introduction.pdf)
- (Lecture1-2_finiteautomata.pptx) (Lecture1-2_finiteautomata.pdf)
2020.10.13 Strings, languages
- (Lecture2-1_strings.pptx) (Lecture2-1_strings.pdf)
- (Lecture2-2_languages.pptx) (Lecture2-2_languages.pdf)
2020.10.20 Regular languages
- (Lecture3-1_automatonoperations.pptx) (Lecture3-1_automatonoperations.pdf)
- (Lecture3-2_nfa.pptx) (Lecture3-2_nfa.pdf)
2020.10.27 Nondeterministic finite automata, regular operations
- (Lecture4-1_nfalanguages.pptx) (Lecture4-1_nfalanguages.pdf)
- (Lecture4-2_nfa2dfa.pptx) (Lecture4-2_nfa2dfa.pdf)
2020.11.12 Regular expressions
- (Lecture5-1_regularoperations.pptx) (Lecture5-1_regularoperations.pdf)
- (Lecture5-2_regularexpressions.pptx) (Lecture5-2_regularexpressions.pdf)
2020.11.17 Nonregular languages, pumping lemma
- (Lecture6-1_pumpingregular.pptx) (Lecture6-1_pumpingregular.pdf)
- (Lecture6-2_cfg.pptx) (Lecture6-2_cfg.pdf)
2020.11.24 Context-free grammars, context-free languages, pushdown automata
- (Lecture7-1_cfl.pptx) (Lecture7-1_cfl.pdf)
- (Lecture7-2_pda.pptx) (Lecture7-2_pda.pdf)
2020.12.01 Non-context-free languages, pumping lemma
- (Lecture8-1_pdacfl.pptx) (Lecture8-1_pdacfl.pdf)
- (Lecture8-2_pumpclf.pptx) (Lecture8-2_pumpclf.pdf)
2020.12.08 Turing machines
- (Lecture9-1_tm.pptx) (Lecture9-1_tm.pdf)
- (Lecture9-2_config.pptx) (Lecture9-2_config.pdf)
2020.12.15 Turing-recognizable languages, Turing-decidable languages, variants of Turing machines
- (Lecture10-1_tmlanguage.pptx) (Lecture10-1_tmlanguage.pdf)
- (Lecture10-2_tmvariants.pptx) (Lecture10-2_tmvariants.pdf)
2020.12.22 Algorithms, decidable problems, decidability
- (Lecture11-1_computability.pptx) (Lecture11-1_computability.pdf)
- (Lecture11-2_decidability.pptx) (Lecture11-2_decidability.pdf)
2021.01.12 Undecidable problems
- (Lecture12-1_undecidability.pptx) (Lecture12-1_undecidability.pdf)
- (Lecture12-2_undecidableproblems.pptx) (Lecture12-2_undecidableproblems.pdf)
2021.01.19 Time complexity, P and NP
- (Lecture13-1_complexity.pptx) (Lecture13-1_complexity.pdf)
- (Lecture13-2_np.pptx) (Lecture13-2_np.pdf)
2021.01.26 NP completeness
- (Lecture14-1_npcomplete.pptx) (Lecture14-1_npcomplete.pdf)
- (Lecture14-2_completelanguage.pptx) (Lecture14-2_completelanguage.pdf)

Video lectures

Week 1 (two video lectures)

Lecture 1-1

Lecture 1-2

Week 2 (two video lectures)

Lecture 2-1

Lecture 2-2

Week 3 (two video lectures)

Lecture 3-1

Lecture 3-2

Week 4 (two video lectures)

Lecture 4-1

Lecture 4-2

Week 5 (two video lectures)

Lecture 5-1

Lecture 5-2

Week 6 (two video lectures)

Lecture 6-1

Lecture 6-2

Week 7 (two video lectures)

Lecture 7-1

Lecture 7-2

Week 8 (two video lectures)

Lecture 8-1

Lecture 8-2

Week 9 (two video lectures)

Lecture 9-1

Lecture 9-2

Week 10 (two video lectures)

Lecture 10-1

Lecture 10-2

Week 11 (two video lectures)

Lecture 11-1

Lecture 11-2

Week 12 (two video lectures)

Lecture 12-1

Lecture 12-2

Week 13 (two video lectures)

Lecture 13-1

Lecture 13-2

Week 14 (two video lectures)

Lecture 14-1

Lecture 14-2

For 2019 course see here.
For 2018 course see here.