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
• Finite Automata: lec3.pdf, lec4.pdf, lec5.pdf
• Regular Expressions: lec6.pdf, lec7.pdf
• Properties of Regular Languages: lec8.pdf, lec9.pdf
• (Part 2) Pushdown Automata
• Context-free languages: lec10.pdf, lec11.pdf
• Pushdown automata: lec12.pdf, lec13.pdf
• Properties of Context-free Languages: lec14.pdf, lec15.pdf
• (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