



THEORY OF COMPUTATION
Group A
Regular sets and regular expression, deterministic and nondeterministic and finite automata,
equivalent finite automation of both. Minimization of states for deterministic finite automata.
Chomsky hierarchy of grammars, equivalent contextfree grammars.
Chomsky normal form, recursiveness of contextsensitive grammar, syntaxdirected
translations.
Pushdown automata, pumping lemma for contextfree 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, NPcompleteness concepts and some standard NPcomplete problems.






© Copyright 2008. All right reserved  AMIE Students


