MA6200 Theory of Computation

Course Details

Grammars and Languages: Language basics, Regular expressions, Regular grammars, Contextfree grammars, context-sensitive grammars, unrestricted grammars, Chomsky hierarchy. Automata: Finite automata, pushdown automata, Pumping Lemmas and Closure properties, Turing machines and recursively enumerable languages. Computability: Computable functions, non-recursively enumerable languages, Undecidability, Rice's theorem, Post's correspondence problem, Undecidability of validity problem of First Order Logic. Complexity: Asymptotic order symbol, Space and Time complexity, Classes P and NP, NP-completeness, Cook-Levin tehorem, Other NP-complete problems.

Course References:

Text Books: 1. K.Krithivasan and R.Rama, Introduction to Formal Languages, Automata and Computation, Pearson Education, 2009. 2. A.Singh, Elements of Computation Theory, Springer (In: Texts in Computer Science Series),2009.