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: Wed 0900--1000, Wed 1000--1100, Fri 1400--1500; (COM1--208)
Mid Term Dates: 13 Mar 2008 6:00 PM and 10 April 6:00 PM. Location: COM1-204. Note that Midterm will be 1 hour long.
Syllabus for 1st midterm: Regular Languages (including DFA/(epsilon)-NFA/ Regular expressions/pumping lemma/right (left) linear grammars. [Everything done in first four weeks of lectures/tutorials + left/right linear grammars]
Prerequisites: Students should already be familiar with material from Discrete Mathematics/Discrete Structures (CS1231). Knowledge of algorithms and programming is also useful.
J. Hopcroft, R. Motwani and J. Ullman, Introduction to Automata Theory, Languages and Computation. 3nd Edition, Addison-Wesley, 2007.
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 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.
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.
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.
Mid Term Dates: 13 Mar 2008 6:00 PM and 10 April 6:00 PM. Location: COM1-204. Note that Mid Term will be 1 hour long.
Final Exam Date: Currently scheduled for May 6th (Final exam will be 2 hour long).