THEORY OF COMPUTATION
Group A

Regular sets and regular expression, deterministic and non-deterministic and finite automata,
equivalent finite automation of both. Minimization of states for deterministic finite automata.
Chomsky hierarchy of grammars, equivalent context-free grammars.
Chomsky normal form, recursiveness of context-sensitive grammar, syntax-directed
translations.
Pushdown automata, pumping lemma for context-free languages, automata for syntax-
directed translations.

Group B


Turing machines and its variants, universal luring machines, recursive functions and sets.
Equivalence of recursive functions and computable functions.
Complexity theory. Space complexity, time complexity, simulation of RAM by TM and its
complexity, NP-completeness concepts and some standard NP-complete problems.

 

© Copyright 2008. All right reserved - AMIE Students