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