# CS2200 Languages, Machines, and Computation

Jan - May 2020

#### Coordinates

- Where: CS 36
- When: D slot (Mon 11-11.50, Tue 10-10.50, Wed 9-9.50, Thu 13-13.50)

#### TAs

- Anil Kumar S (cs18d001@smail)
- Anoop S K M (cs18d003@smail)
- Athul M A (cs19m015@smail)
- Govind Sankar (ee16b109@smail)
- Sampriti Roy (cs18s007@smail)
- Sreyas S (cs18d010@smail)

#### Objectives

This course provides an introduction to the mathematical theory of computation. The course gives a preliminary exposure to theoretical computer science, and the formal relationships among machines and computational problems with the aim of understanding the nature of computation and its inherent limits.

#### Contents

The following is a brief overview of the topics that will be covered in this course. The order of the topics covered may vary. - **Finite-State Machines and Regular Languages**: Languages vs Computational problems, Deterministic and non-deterministic finite state automata, regular languages, closure properties, limitations - pumping lemma and Myhill-Nerode relations, state minimization, equivalent models, algorithmic questions. - **Context-Free Grammars**: Grammars, Chomsky hierarchy, normal forms, closure properties, limitations - pumping lemma, algorithmic questions - parsing algorithm, equivalent models - push-down automata. - **Computability Theory** - Turing machines, equivalence between different variants, Universal Turing machine, recursively enumerable and recursive sets of languages, Decidability - Halting Problem, Post’s correspondence problem, Rice’s theorem, Church-Turing thesis. - **Basic Complexity Theory** - Measures of complexity, complexity classes P and NP, notion of polynomial-time reducibility, NP-completeness, satisfiability and Cook’s theorem.

#### References

**[K]**:*Automata and Computability*-*Dexter C. Kozen***[HMU]**:*Introduction to Automata Theory, Languages and Computation*-*Hopcroft, Motwani and Ullman.***[S]**:*Introduction to the Theory of Computation*-*Michael Sipser*

#### Grading policy

- Pop quizzes: 5%
- Short exams: 3*5 = 15%

- Quizzes: 2*20 = 40%
- End-sem: 40%

#### Important dates

- Short exams: Feb 6, Mar 12
- Quizzes: Feb 20

#### Course Materials

- Moodle
- Lectures and references