Theory of Computation

Course Objectives :

1. To understand Automata (Deterministic and Non-Deterministic) and Language Theory
2. To understand Context Free Grammar (CFG), Parse Trees and Push Down Automata
3. To introduce the concepts of Turing Machines and Computability Theory
4. To understand Complexity Theory (NP-completess NP-hardness) and Space complexity

Course Outcomes (CO)

• CO1 Ability to understand the design aspects of “abstract models” of computers like finite automata, pushdown automata, and Turing machines.
• CO2 Ability to comprehend the recognizability (decidability) of grammar (language) with specific characteristics through these abstract models.
• CO3 Ability to decide what makes some problems computationally hard and others easy?
• CO4 A ability to deliberate the problems that can be solved by computers and the ones that cannot?

UNIT – I

Automata and Language Theory: Chomsky Classification, Finite Automata, Deterministic Finite Automata (DFA), Non-Deterministic Finite Automata (NFA), Regular Expressions, Equivalence of DFAs, NFAs and Regular Expressions, Closure properties of Regular grammar, Non-Regular Languages, Pumping Lemma.

UNIT – II

Context Free Languages: Context Free Grammar (CFG), Parse Trees, Push Down Automata (deterministic and non-deterministic) (PDA), Equivalence of CFGs and PDAs, Closure properties of CFLs, Pumping Lemma, Parsing, LL(K) grammar.

UNIT – III

Turing Machines and Computability Theory: Definition, design and extensions of Turing Machine, Equivalence of various Turing Machine Formalisms, Church – Turing Thesis, Decidability, Halting Problem, Reducibility and its use in proving undecidability. Rices theorem. Undecidability of Posts correspondence problem., Recursion Theorem.

UNIT – IV

Complexity Theory: The class P as consensus class of tractable sets. Classes NP, co-NP. Polynomial time reductions. NP-completess, NP-hardness. Cook- Levin theorem (With proof). Space complexity, PSPACE and NPSPACE complexity classes, Savitch theorem (With proof). Probabilistic computation, BPP class. Interactive proof systems and IP class. relativized computation and oracles.

Textbook(s):

1. Sipser, Michael. Introduction to the Theory of Computation, Cengage Learning, 2012.
2. J. Hopcroft, R. Motwani, and J. Ullman, Introduction to Automata Theory, Language and Computation, Pearson, 2nd Ed, 2006.

References:

1. Peter Linz, An Introduction to Formal Languages and Automata, 6th edition, Viva Books, 2017
2. Maxim Mozgovoy, Algorithms, Languages, Automata, and Compilers, Jones and Bartlett, 2010.
3. D. Cohen, Introduction to Computer Theory, Wiley, N. York, 2nd Ed, 1996.
4. J. C. Martin, Introduction to Languages and the Theory of Computation, TMH, 2nd Ed. 2003.
5. K. L. Mishra and N. Chandrasekharan, Theory of Computer Science: Automata, Languages and Computation, PHI, 2006.
6. Anne Benoit, Yves Robert, Frédéric Vivien, A Guide to Algorithm Design: Paradigms, Methods, and Complexity Analysis, CRC Press, 2013.