Theory of Computation

Instructor

• Reza Pulungan

Schedule

• Lectures
  • Wednesdays: 13:00-15:30, at SIC 3.02
• 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 22, 2012)

• Introduction
• DFA

Lecture 1 (February 29, 2012)

• NFA

Lecture 2 (March 7, 2012)

• epsilon-NFA
• RE
• Exercise 1 (Due: March 21, 2012)

Lecture 3 (March 14, 2012)

• RE

Lecture 4 (March 21, 2012)

• Pumping Lemma + CFG

Lecture 5 (March 28, 2012)

• CFG + PDA
• Exercise 2 (Due: Mid-Term)

Lecture 6 (April 4, 2012)

• PDA + Simplifying Grammar

MID-TERM (April 20, 2012)

Lecture 7 (May 2, 2012)

• Pumping Lemma for CFL + Decidability Theory

Lecture 8 (May 9, 2012)

• Decidability Theory + Turing Machine

Lecture 9 (May 23, 2012)

• Turing Machine

Lecture 10 (May 30, 2012)

• Non-Deterministic Turing Machine

Lecture 11 (June 13, 2012)

• Undecidability
• Exercise 3