NIT Srinagar Syllabus 6th Sem
Theory of Computation
Complexity of computations, automata , computability, complexity, mathematical notions and terminology, definitions, theorems and proofs, types of proofs
Automata & Languages:
Finite Automata, Non-determinism, regular expressions, non-regular expressions
Context free languages:
context free grammar, pushdown automata, non-context free languages, equivalences, closure properties, concepts in parsing,
uring machines, variants of turing machines, the definition of algorithm.
Decidability, reducibility, advanced topics in computability theory- recursion theorem etc.
Complexity theory-time complexity, space complexity, intractability.
- C. Papadimitrou and C. L. Lewis. Elements of Theory of Computation , Prentice-Hall, 1981.
- J.E. Hopcroft and J.D. Ullman. Introduction to Antomata Theory,
- Languages of Computations , Addison-Wesley, 1979. (Indian edition available from Narosa.)