NIT Srinagar Syllabus 6th Sem CSE Theory of Computation

NIT Srinagar Syllabus 6th Sem

Theory of Computation

 

Introduction:
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,

Computability theory:
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.

Books Recommended:

  1. C. Papadimitrou and C. L. Lewis. Elements of Theory of Computation , Prentice-Hall, 1981.
  2. J.E. Hopcroft and J.D. Ullman. Introduction to Antomata Theory,
  3. Languages of Computations , Addison-Wesley, 1979. (Indian edition available from Narosa.)

Leave a Comment