Theory of Computation, 2016 Spring
Course Information
- Instructor: Hakjoo Oh
- TAs: Sungjoon Hong, Kwonsoo Chae
- Lecture: 9:00-10:15 on Tuesdays and Thursdays
- Syllabus
Textbook
- Introduction to Automata Theory, Languages, and Computation (Third Edition)
Slides
- Introduction: lec0.pdf
- Preliminaries: lec1.pdf, lec2.pdf
- Finite Automata: lec3-1.pdf, lec3-2.pdf, lec3-3.pdf
- Regular Expressions: lec4.pdf, lec5.pdf
- Properties of Regular Languages: lec6.pdf, lec7.pdf
- Context-free languages: lec8.pdf, lec9.pdf
- Pushdown automata: lec10.pdf, lec11.pdf
- Properties of Context-free Languages: lec12.pdf, lec13.pdf
- Turing Machines: lec14.pdf, lec14-examples.pdf, lec15.pdf, lec15-examples.pdf
- Undecidability: lec16.pdf lec17.pdf
- Review: lec18.pdf
Homework
- HW 1: DFA, NFA, and e-NFA (due 3/31)
- HW 2: Regular Expresssions, Properties of Regular Languages (due 4/12)
- HW 3: Context-Free Languages, Pushdown Automata (due 5/12)
- HW 4: Essay (due 6/2) 우수에세이: 2015410126, 2015410056, 2015410047, 2011160004
Exams
- Past: mid2015.pdf, final2015.pdf
Software Analysis Lab. @ Korea University