CS3231 : Theory of Computation
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.
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.
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).
Name :
Rahul Jain
Office :
S15-04-01
Email:
first name at comp.nus.edu.sg
Phone:
65168826 (off).
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.
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.
Turing machine lectures from last year:
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.