<h3>MA6200 THEORY OF COMPUTATION (modified)</h3>
<br/>
<h4>Course Details</h4>
Grammars and Languages: Language basics, Regular expressions, Regular grammars, Contextfree grammars, context-sensitive grammars, unrestricted grammars, Chomsky hierarchy.<br><br>  Automata: Finite automata, pushdown automata, Pumping Lemmas and Closure properties, Turing machines and recursively enumerable languages.<br><br>  Computability: Computable functions, non-recursively enumerable languages, Undecidability, Rice's theorem, Post's correspondence problem, Undecidability of validity problem of First Order Logic.<br><br>  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: <br>
1. K.Krithivasan and R.Rama, Introduction to Formal Languages, Automata and Computation, Pearson Education, 2009. <br>
2. A.Singh, Elements of Computation Theory, Springer (In: Texts in Computer Science Series),2009.