Lecturer: Sanjay Jain. (COM2 03-59; sanjay@comp.nus.edu.sg)
Office Hours: Friday 4--5pm (or by appointment)
Lectures: Fri 10--12
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.
Mid Term 1: September 19, 6PM. Duration 1 hour. Location: COM1-02-06 SR1
Tentative 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: October 24, 6PM. Duration 1 hour. Location: COM1-02-06 SR1
Tentative 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. Duration 2 hours.
J. Hopcroft, R. Motwani and J. Ullman, Introduction to Automata Theory, Languages and Computation. 3rd Edition, Pearson, 2014.
H. Lewis and C. Papadimitriou. Elements of the Theory of Computation, 2nd Edition, Prentice Hall, 1998.
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
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.
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 by XXX midnight for the YYY tutorial class. The tutorial answers should be submitted in the Canvas module Files folder corresponding to the tutorial (so T1 is for Tutorial 1). The name of your pdf file for Tutorial 1 should be in the format: A1234567B-T1.pdf where A1234567B is your student number. Similarly, for Tutorial number i, replace T1 by Ti. 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.