Theory of Computation

Course Objective: Theory of computation deals with encapsulation and abstraction of diverse computational processes, be it hardware or software that enables us to compare them and understand their basic capabilities and limitations. It is intrinsically related to algorithmic models, where we seek to determine what can and cannot be computed, how quickly, with how much memory without being bogged down by low-level implementation details. The students will
1. learn conceptual tools that practitioner use and argue about many fundamental computational questions in a rigorous framework.
2. be introduced to Chomsky hierarchy of formal languages that involve understanding of core techniques like simulation, reductions and non-determinism.
3. get a deeper understanding of what is hard to compute efficiently and trade-offs between resources like time and space even for the fastest computing machines.

Pre-requisites: Discrete Mathematics, Data Structures and algorithms and Design and Analysis of Algorithms (highly recommended)

Coverage: The course will cover key topics in Automata and Languages, Computability Theory, and Complexity Theory. The topics include:
– Automata and Languages Regular Languages: Finite Automata, Non-determinism, Regular expressions, Non-regular languages, Myhill Nerode theorem and DFA Minimization
Context Free Languages: Context free grammar and normal forms, Push down automata, Equivalence of CFL and PDA, Pumping lemma for proving non-regularity and Non-CFL, Deterministic CFL and non-CFL (optional)
– Computability Theory
Turning Machine and variations including Stack and counter machines Decidability: Decidable Language, Undecidability, basic Rice’s theorem, Reducibility and its application to proving undecidability
– Complexity Theory
Time and Space Complexity and their relationship in the context of DTM and NDTM, Complexity Classes: P, NP, PSPACE, Randomized complexity classes (optional) Polynomial Reducibility NP Hardness, NP-completeness, Cook-Levin theorem for Satisfiability and some common NP complete problems