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 cont ext-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 functi ons 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.