Advanced Theory of Computation

Introduction:The course aims to introduce students to the mathematical foundations of computation including automata theory; the theory of formal languages and grammars; the notions of algorithm, decidability, complexity, and computability. Several mathematical models of computation have been formulated independently and under any such computational model, the existence of well-defined but unsolvable problems can be formally shown. These topics form part of the core of the mathematical foundations of computer science that will provide students and researchers with a sound theoretical view of the most fundamental concepts of computation. Specifically, this course provides a rigorous introduction to the theoretical foundations of computer science. It deals with a number of interconnected topics and tries to answer the basic questions, "What is a computer?", "What is an algorithm?", and "What is computable?". This course examines important theorems and proofs, establishes a number of interesting assertions in order to expose the techniques used in the area of theory of computation. Note that although this is not a "mathematics" course, it does make significant use of mathematical structures, abstractions, definitions, theorems, proofs, lemmas, corollaries, logical reasoning, inductive proofs, and the like. If such concepts are difficult for you, you will find this course very difficult but rewarding.

Course Code: CSCC-7401

Credit Hours: 03

Prerequisites: Nil

Learning outcome: Upon successful completion of this course, you will be able to

discuss key notions of computation, such as algorithm, computability, decidability, reducibility, and complexity, through problem solving.
explain the models of computation, including formal languages, grammars and automata, and their connections.
state and explain the Church-Turing thesis and its significance.
analyze and design finite automata, pushdown automata, Turing machines, formal languages, and grammars.
solve computational problems regarding their computability and complexity and prove the basic results of the theory of computation.

Contents:

Mathematical Tools and Techniques: Logic and Proofs, Sets, Functions and Equivalence Relations, Languages.
Proofs, Principle of Mathematical Induction, Recursive Definitions, Structural Induction.
Regular Languages and Regular Expression.
Nondeterministic Finite Automata with A-Transitions, Kleene’s Theorem.
Regular, Non-regular Languages, Criteria for Regularity, Minimal Finite Automata
Context-Free Grammars, Regular Grammars, Derivation Tree and Ambiguity
Pushdown Automata: Definitions and Examples, Deterministic Pushdown Automata
Context-Free, Non-Context-Free Languages.
Turing Machines: Definitions and Examples, Non-deterministic TM, Universal TM
Recursively Enumerable and Languages: Recursively Enumerable and Recursive, Enumerating a Language, More General Grammars, Context-Sensitive Languages and the Chomsky Hierarchy
Unsolvable Problems: A No-recursive Language and an Unsolvable Problem, The Halting Problem, Unsolvable Problems Involving TMs, Rice’s Theorem, Post’s Correspondence Problem
Computable Functions: Primitive Recursive Functions, PRF and Bounded Operations, Unbounded. Minimalization and ų-Recursive Functions, Godel Numbering

Recommended Texts:

John Martin. (2010). Introduction to languages and the theory of computation, (4th ed.). New York: McGraw-Hill Science/Engineering/Math.
Tourlakis, George J. (2012). Theory of computation. Hoboken: Wiley.

Suggested Readings:

Goddard, W. (2008). Introducing the theory of computation. ‎Burlington: Jones and Bartlett Publishers, Inc.
Dexter C. Kozen . (2010). Theory of computation, (1st ed.). New York: Springer.

Assesment Criteria:

Sessional: 20

Assignment 1 04 marks

Assignment 2 04 marks

Quiz 1 04 marks

Quiz 2 04 marks

Attendance 04 marks

Mid Term: 30

Final exam: 50

Class Timing :

MSCS 1st Self

Thursday 11: 00 am - 2: 00 pm