CS3231 : Theory of Computation

Course Information

This module serves as an introduction to

1) some standard formal models of computation so as to develop an understanding of what can and cannot be computed by various devices and their relation to formal languages,

2) some techniques in computer science (e.g. nondeterminism, diagonalization, simulation and reduction),

3) the mathematical formulation of objects in computer science so as to study their properties.

Topics :

 

Preliminaries: Algebra and languages. Operations on strings. The countability of strings and uncountability of languages.

Regular Languages and Finite Automata: Regular expressions. Deterministic and non-deterministic finite state automata and their equivalence. Equivalence to regular languages. Closure properties (union, complementation, Kleene star). Pumping Lemma. Decision algorithms.

Context-Free Languages and Pushdown Automata: Context free grammars. Regular languages are context-free. Chomsky Normal Form. Pumping Lemma. Decision algorithms. Closure properties (union, concatenation, Kleene star, intersection with regular set). The equivalence of context-free languages and pushdown automata.

Turing Machines: Programming Turing machines. Acceptance, recognition and computation by Turing machines. Multiple tapes and non-determinism do not add power. Church-Turing Thesis. Universal Turing machines. Chomsky Hierarchy. Decidability: Halting and other problems. Undecidability: Rice's theorem.

There are no pre-requisites for the course and we will keep it as self contained as possible.

Logistics:

 

Lectures: Every Thursday 2-4pm at LT15. First lecture on 12th August, 2010.

 

Tutorials: Every Monday 3-5pm at COM1/217. First tutorial on 23rd August, 2010.

 

Office Hours: Every Thursday 11-12pm (or by appointment).

Lecturer:

 

Name : Rahul Jain

Office : S15-04-01

Email: first name at comp.nus.edu.sg

Phone: 65168826 (off).

Books:

 

We will use the following as textbook. All of what we will study will be from this book.

 

Title: “Introduction to the theory of computation” (Second Edition).

Author:  Michael Sipser.

 

You may use the following as an alternate text for your own reference:

 

Title: “Introduction to Automata Theory, Languages and Computation.” (Third Edition)

Authors: J. Hopcroft, R. Motwani and J. Ullman,

Publisher: Addison-Wesley, 2007.

Evaluations :

 

There will be two midterms and one final examination. All these will be open book. Each of the midterms are worth 25 points. Final exam is worth 50 points.

 

Lecture notes:

 

These are lecture notes using power-point slides. You are encouraged to also take your own notes.

 

Lecture 1 - 11.

 

Turing machine lectures from last year:

 

Lecture 1

Lecture 2

Lecture 3

 

Tutorials:

 

Each tutorial will be given to you during the lecture. You may hand in your tutorial solutions at the start of your tutorial class (this is not necessary but is encouraged). I will check the handed in tutorial solutions and hand them over back in the next lecture (there are no marks for these). You may discuss tutorials with your friends, however you should write the answers on your own. You would be randomly asked to present some questions during the tutorial class. Besides the tutorials, you are encouraged to work on several problems given in the text book.

 

Tutorial 1

 

Tutorial 2

 

Tutorial 3

 

Tutorial 4

 

Tutorial 5

 

Tutorial 6

 

Tutorial 7

 

Tutorial 8