MA6200     THEORY OF COMPUTION

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.

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.