Theory of Computation, 2017 Spring
Course Information
- Instructor: Hakjoo Oh
- TAs: Sungjoon Hong, Junhee Lee
- Lecture: 9:00-10:15 on Mondays and Wednesdays
Textbook
- Introduction to Automata Theory, Languages, and Computation (Third Edition)
Slides
- Introduction: lec0.pdf
- Mathematical Preliminaries: lec1.pdf, lec2.pdf
- (Part 1) Finite Automata
- (Part 2) Pushdown Automata
- (Part 3) Turing Machines and Computability
- Standard Turing Machines: lec16.pdf, lec17-examples.pdf
- Extensions: lec18.pdf, lec19-examples.pdf
- Undecidability: lec20.pdf
- P and NP: lec21.pdf
- Review: lec22.pdf
Homework
- HW 1: DFA, NFA, and e-NFA (due 3/29)
- HW 2: Regular Expresssions, Properties of Regular Languages (due 4/17)
- HW 3: Context-free Languages (due 5/29)
Exams
- Past: mid2015.pdf, final2015.pdf
Software Analysis Lab. @ Korea University