Theory of Computation, 2018 Spring
Course Information
- Instructor: Hakjoo Oh
- TAs: Sooyoung Cha, Seonho Lee
- Lecture: 14:00-15:15 on Tuesdays and Thursdays
Textbook
- Introduction to Automata Theory, Languages, and Computation (Third Edition)
Slides
- Introduction: lec0.pdf
- 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, lec10.pdf
- Pushdown automata: lec11.pdf, lec12.pdf
- Properties of Context-free Languages: lec13.pdf, lec14.pdf
- (Part 3) Turing Machines and Computability
- 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: DFA, NFA, and e-NFA (due 4/3)
- HW 2: Regular expressions and languages (due 4/19)
- HW 3: Context-free languages (due 5/24)
- HW 4: Essay (due 6/12)
- Excellent essays from previous years: 2015410126, 2015410056, 2015410047, 2011160004