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.

Syllabus:

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	15 % (3* 5%)
Quiz - 1	20 %
Quiz - 2	20 %
End Semester Exam	45%
Bonus problem sets	5% ( Extra)