# 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:

- 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.)