CS3231: Theory of Computation

Lecturer: Sanjay Jain. (COM1 03-36; sanjay@comp.nus.edu.sg)

Office Hours: Thu 11:00--11:55 (or by appointment)

Lectures: Thu 1200--1400; COM1-204.

Tutorials: Fri 3--4 and 4--5.

Mid Term Dates:

Mid Term 1: Mar 6th, 6PM (Location: COM1/206)

Syllabus for Mid Term 1: All topics related to Regular Languages (including DFA, NFA, e-NFA, minimization of number of states, pumping lemma, regular expressions, closure properties etc). In Lectures: this was done in Weeks 1--4, plus little bit in Week 5. In text book (3rd edition) this is chapters 1--4.

Mid Term 2: Mar 30th, 6PM (Location: COM1/208)

Syllabus for Mid Term 2: All topics related to Context Free Languages (including CFG, PDA, DPDA, properties, removal of useless symbols, CNF, pumping lemma, etc).

Prerequisites: Students should already be familiar with material from Discrete Mathematics/Discrete Structures (CS1231). Knowledge of algorithms and programming is also useful.

Text Book

J. Hopcroft, R. Motwani and J. Ullman, Introduction to Automata Theory, Languages and Computation. 3nd Edition, Addison-Wesley, 2007.

Additional References

H. Lewis and C. Papadimitriou. Elements of the Theory of Computation, 2nd Edition, Prentice Hall, 1998.

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.

This course covers three main topics:

(i) Finte State Automata and Regular Languages,

(ii) Push Down Automata and Context Free Lanuguages,

(iii) Turing Machines, Church-Turing Thesis, and Unsolvability.

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 nondeterminism do not add power. Church-Turing Thesis. Universal Turing machines. Chomsky Hierarchy.

Decidability: Halting and other problems. Undecidability. Rice's theorem.

Assignements and Tutorials

Tutorials will hopefully start in the second week of the semester. There will be 11 to 12 tutorials in total.

Each tutorial will be given to you during the lecture, and you should hand in your tutorials at the start of your tutorial class. 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 book and other references.

Midterms and Final Examination

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.

Final Exam Date: Currently scheduled for April 29th (Final exam will be 2 hour long).