<h3>MA6200 Theory of Computation</h3>
<br/>
<h4>Course Details</h4>
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.
<br/>
<h4>Course References:</h4>
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.