Basic Information

Course Objectives:

To introduce students the basic concepts in theoretical computer science, and the formal relationships among machines, languages and grammars and computational problems.


The following is the syllabus for the course as per the curriculum.

Finite Automata & Regular Languages : Introduction to automata theory, languages and computational problems. Finite state automata, Regular Languages. Deterministic and Non-deterministic finite automata, Subset construction. Regular Expressions, Pattern Matching.
Context Free Languages and Push Down Automata : Grammars - Production systems - Chomskian hierarchy - Context free grammars - Normal forms - uvwxy theorem - Parikh mapping - Self embedding property - subfamilies of CFL - Derivation trees and ambiguity. Pushdown automata - Acceptance by empty store and final state - Equivalence between push-down automata and context-free grammars - Closure properties of CFL - Deterministic push-down automata - Parsing - CYK algorithm

Turing machines & Computability - Techniques for Turing machine construction - Generalized and restricted versions equivalent to the basic model - Universal Turing machine - Recursively enumerable sets and recursive sets - Context sensitive languages and linear bounded automata. Decidability; Post's correspondence problem; Rice's theorem; decidability of membership, emptiness and equivalence problems of languages.

Basic Complexity Theory : Time and tape complexity measures of Turing machines; Random access machines; the classes P and NP; NP-completeness; Satisfiability and Cook's theorem; Polynomial reduction and some NP-complete problems.

Evaluation Scheme

Activity Weight
Short Exams 20 % (2* 10%)
Quiz - 1 20 %
Quiz - 2 20 %
End Semester Exam 40%
Bonus problem sets 5% ( Extra)