Theory of Computation

Instructor

• Reza Pulungan

Schedule

• Lectures
  • Class B: 13:00-15:30, at SIC 3.02
  • Class C: 07:30-10:10, 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 22, 2010)

• Introduction
• Finite State Machines 1

Lecture 1 (March 1, 2010)

• Finite State Machines 2
• Exercise 1 (due March 8, 2010)

Lecture 2 (March 8, 2010)

• Finite State Machines 3 + Regular Expressions

Lecture 3 (March 15, 2010)

• Regular Expressions + Pumping Lemma

Lecture 4 (March 22, 2010)

• Bukti Pumping Lemma + Minimisasi DFA + CFG
• Exercise 2 (due March 29, 2010)

Lecture 5 (March 29, 2010)

• CFG + PDA

Lecture 6 (April 5, 2010)

• PDA + PDA & CFG + DPDA
• Exercise 3
• Solution of Exercise 1
• Solution of Exercise 2
• Solution of Exercise 3

Lecture 7 (April 19, 2010)

• Menyederhanakan CFG

Lecture 8 (April 26, 2010)

• Decidabilitas

Lecture 9 (May 3, 2010)

• Mesin Turing

Lecture 10 (May 10, 2010)

• Mesin Turing

Lecture 11 (May 17, 2010)

• Algoritma dan Procedure
• Exercise 4 (due May 24, 2010)

Lecture 12 (May 23, 2010)

• Post's Correspondence Problem
• Solution of Exercise 4
• Exercise 5
• Solution of Exercise 5