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.
|Short Exams||20 % (2* 10%)|
|Quiz - 1||20 %|
|Quiz - 2||20 %|
|End Semester Exam||40%|
|Bonus problem sets||5% ( Extra)|