Theory of Computation, 2019 Spring
Course Information
- Instructor: Hakjoo Oh
- TAs: Seongjoon Hong and Junhee Lee (Class 02), Myungho Lee and Donghun Jeon (Class 03)
- Lecture: 14:00-15:15 (Class 02), 15:30-16:45 (Class 03) on Mondays and Wednesdays
Textbook
- Introduction to Automata Theory, Languages, and Computation (Third Edition)
Slides
- Introduction: lec0.pdf
- Mathematical Preliminaries: lec1.pdf
- (Part 1) Finite Automata
- Finite Automata: lec2.pdf, lec3.pdf, lec4.pdf
- Regular Expressions: lec5.pdf, lec6.pdf
- Properties of Regular Languages: lec7.pdf, lec8.pdf
- (Part 2) Pushdown Automata
- Context-free languages: lec9.pdf, lec9-2.pdf, lec10.pdf
- Pushdown automata: lec11.pdf, lec12.pdf
- Properties of Context-free Languages: lec13.pdf, lec14.pdf
- (Part 3) Turing Machines and Computability
- The Origin of Computer Science: 15-0.pdf
- Standard Turing Machines: lec15.pdf, lec16.pdf
- Extensions: lec17.pdf, lec18.pdf
- Undecidability: lec19.pdf
- P, NP, and NP-completeness: lec20.pdf
- Review: lec21.pdf
Homework
- HW 1: Finite Automata (due 4/3, in class)
- HW 2: Regular Expressions/Languages (due 4/17)
- HW 3: Context-free languages (due 5/22)
- HW 4: Essay (due 6/10)