Theory of Computation

Instructor

• Reza Pulungan

Schedule

• Lectures
  • Class B: Thursdays: 10:00-12:30, at SIC 3.04
  • Class C: Wednesdays: 13:00-15:30, at SIC 3.01
• Exams
  • Mid-term:
  • Final:

Objectives

Syllabus

Textbooks

• J. Hopcroft, R. Motwani, and J. Ullman, Introduction to Automata Theory, Languages and Computation (2nd ed.), Addison-Wesley, 2001.
• M. Sipser, Introduction to the Theory of Computation (2nd ed.), Thompon Course Technology, 2006.

Grading

• Exercises: 20%
• Mid-term exam: 40%
• Final exam: 40%

Lectures

Lecture 0 (February 16, 2011)

• Introduction

Lecture 1 (February 23, 2011)

• Finite State Machines

Lecture 2 (March 2, 2011)

• Regular Expressions

Lecture 3 (March 9, 2011)

• Regular Expressions + Pumping Lemma

Exercise 1 (March 22, 2011)

• Exercise 1 due March 31, 2011

Lecture 4 (March 23, 2011)

• Pumping Lemma + DFA Minimization

Lecture 5 (March 30, 2011)

• CFG + PDA

Lecture 6 (April 6, 2011)

• CFG + PDA

Lecture 7 (April 20, 2011)

• Menyederhanakan Grammar + CNF