Instructor: Dr. Avijit Dutta
Course Objective: Automata theory deals with the logic of computation with respect to simple machines, referred to as automata. This is an abstract model of machines that perform computations on an input by moving through a series of states or configurations. At each state of the computation, a transition function determines the next configuration on the basis of a finite portion of the present configuration. As a result, once the computation reaches an accepting configuration, it accepts that input. Through this course, the students should be able to understand how machines compute functions and solve problems and more importantly, what it means for a function to be defined as computable or for a question to be described as decidable.
Detailed Syllabus
Automata and Languages: Finite Automata, Regular Languages, Reg-
ular Expressions, Deterministic and Non-deterministic Finite Automata, Minimization of Finite Automata, Closure Properties, Kleene’s Theorem, Pumping Lemma and Its Applications, Myhill-Nerode Theorem and Its uses, Decision Algorithms for regular languages
Context-free Grammars: Context free grammars, Derivation trees, Ambiguous grammars, Context-free Languages (CFL), Chomsky Normal Form (CNF), Greibach Normal Form (GNF), Closure Properties, Pumping Lemma for CFL, Linear Grammars, Pumping Lemma for Linear Languages, Push Down Automata, Deterministic Pushdown Automata, Acceptance by empty stack and final state, Decision Algorithms for CFL.
Computability: Turing Machine and variants, Computable Functions, Universality, Halting Problem, Recursive and Recursively Enumerable Sets, Diagonalisation, Reducibility, Rice’s Theorem, Post Correspondence Problem
References:
- Introduction to the Theory of Computations (2nd Edition) Michael Sipser
- An Introduction to Formal Languages and Automata (5th Edition) Peterlinz
- Introduction to Automata Theory, Languages, and Computation (3rd Edition) John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
Classes: Here is a resource for the class lecture notes.
Question paper for Mid-Sem: [Question]
Question paper for End-Sem: [Question]