# Theory of Computation

## Teori Komputasi MIK

## Semester Genap 2011/2012

## Instructor

## Schedule

- Lectures
- Wednesdays: 13:00-15:30, at SIC 3.02

- Exams

## 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)

### Lecture 1 (February 29, 2012)

### Lecture 2 (March 7, 2012)

### Lecture 3 (March 14, 2012)

### Lecture 4 (March 21, 2012)

### Lecture 5 (March 28, 2012)

### 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)

### Lecture 10 (May 30, 2012)

- Non-Deterministic Turing Machine

### Lecture 11 (June 13, 2012)

Reza Pulungan
pulungan@ugm.ac.id