2018/2019, Semester 1

School of Computing (Computer Science)

Modular Credits: 4

(1) somestandard 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 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.

Please see http://www.comp.nus.edu.sg/~sanjay/cs4232.html for regular updates