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