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.