Automata, Languages, Computability and Complexity

Instructor

• Reza Pulungan

Schedule

• Lectures
  • Mondays: 07:00-09:00, M2.10
  • Tuesdays: 11:00-12:00, U2.01
• Exams
  • Mid-term:
  • Final:

Objectives

Syllabus

Textbooks

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

Grading

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

Lectures

Lecture 0 (August 24, 2009)

• Lecture Notes

Lecture 1 (August 25, 2009)

• Lecture Notes
• Exercise 1 (due September 1, 2009)

Lecture 2 (August 31, 2009)

• Lecture Notes

Lecture 3 (September 7, 2009)

• Lecture Notes (in addition to the handwritten notes)

Lecture 4 (September 8, 2009)

• Handwritten Notes
• Exercise 2 (due September 29, 2009. I will certainly collect the solution of this exercise.)

Lecture 5 (September 29, 2009)

• Handwritten Notes

Lecture 6 (October 5, 2009)

• Handwritten Notes

Lecture 7 (October 6, 2009)

• Handwritten Notes
• Exercise 3 (due October 13, 2009.)

Lecture 8 (October 12, 2009)

• Handwritten Notes

Lecture 9 (October 13, 2009)

• Handwritten Notes

Lecture 10 (October 19, 2009)

• Handwritten Notes

Lecture 11 (October 20, 2009)

• Handwritten Notes
• Solution of Exercise 3
• Exercise 4
• Solution of Exercise 4

Lecture 12 (November 9, 2009)

• Handwritten Notes

Lecture 13 (November 10, 2009)

• Handwritten Notes

Lecture 14 (November 23, 2009)

• Handwritten Notes

Lecture 15 (November 24, 2009)

• Handwritten Notes
• Exercise 5 (due December 1, 2009.)

Lecture 16 (November 30, 2009)

• Handwritten Notes

Lecture 17 (December 1, 2009)

• Handwritten Notes

Lecture 18 (December 7, 2009)

• Handwritten Notes

Lecture 19 (December 8, 2009)

• Handwritten Notes
• Exercise 6 (due December 15, 2009.)

Lecture 20 (December 14, 2009)

• Handwritten Notes

Lecture 21 (December 15, 2009)

• Handwritten Notes
• Exercise 7 (due December 22, 2009.)

Lecture 22 (December 21, 2009)

• Handwritten Notes

Lecture 23 (December 22, 2009)

• Handwritten Notes

Lecture 24 (December 28, 2009)

• Handwritten Notes

Lecture 25 (December 29, 2009)

• Handwritten Notes
• Solution of Exercise 5
• Solution of Exercise 6
• Solution of Exercise 7
• CATATAN: Ujian akhir akan dilaksanakan dengan BUKU TERBUKA.