CS4232: Theory of Computation

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

Office Hours: Sanjay Jain: Tue 14:00--15:00 (or by appointment)

Lectures: Tue 1200--1400

Tutorials: Will start in the second week of the semester

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

Exams

Mid Term 1: Sep 14, 6PM

Syllabus for mid term 1: All topics related to Regular languages, including DFA, NFA, epsilon-NFA, Regular expressions, pumping lemma, non-regular languages, closure and other properties of regular languages.

Mid Term 2: Oct 19, 6PM

Syllabus for mid term 2: All topics related to context free languages, including CFG, NPDA, DPDA, normal forms, properties of CFL, pumping lemma, non-context free languages, closure properties, etc. Questions which link regular languages with CFL/CFG/PDA may also be asked.

Final Exam: Syllabus includes everything done throughout the semester in lectures and tutorials.

Text Book

J. Hopcroft, R. Motwani and J. Ullman, Introduction to Automata Theory, Languages and Computation. 3rd Edition, Pearson, 2014.

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 the following 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.

(iv) Space and time complexity of computational problems

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.

Complexity: Time and space complexity. P vs NP, Reductions and NP-completeness.

Assignements and Tutorials

Tutorials will start in the second week of the semester.

Each tutorial will be given to you during the lecture, and you should hand in your tutorials a day before 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.

Lecture Slides

These will be activated/modified as we progress in the semester.

Tutorials