Instructors: Prof. Rana Barua and Dr. Nilanjan Datta
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 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.
Syllabus:
- Automata and Languages: Finite Automata, Regular Languages, Regular 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 Languages (CFL),
Chomsky Normal Form (CNF), Closure Properties, Pumping Lemma for CFL, Push Down Automata, Acceptance by empty stack and final state, Decision Algorithms for CFL. - Computability: Turing Machine and variants, Computable Functions, Primitive and Recursive Functions, Universality, Halting Problem, Recursive and Recursively Enumerable Sets, Diagonalisation, Reducibility.
- Introduction to Complexity: Discussions on Time and Space Complexities, P and NP, NP-completeness, Cook’s Theorem, other NP-Complete Problems, PSPACE.
References:
[1] J. E. Hopcroft, J. D. Ullman and R. Motwani: Introduction to Automata Theory, Languages and Computation, Addison- Wesley, California, 2001.
[2] M. D. Davis, R. Sigal and E. J. Weyuker: Complexity, Computability and Languages, Academic Press, New York, 1994.
[3] M. Sipser: Introduction to The Theory of Computation, PWS Pub. Co., New York, 1999.
[4] H. R. Lewis and C. H. Papadimitriou: Elements of The Theory of Computation, Prentice Hall, Engle-
wood Cliffs, 1981.
[5] M. R. Garey and D. S. Johnson: Computers and Intractability: A Guide to The Theory of NP-Completeness, Freeman, New York, 1979.
Classes (by Prof. Rana Barua):
- Introduction to Deterministic and Non-deterministic Finite Automata. [Class 1]
- Regular Language and Regular Expressions and their properties, Kleene’s Theorem. [Class 2]
Notes (by Prof. Rana Barua):
- Note on Finite Automata, Regular Expressions and Languages [Note 1]
- Note on Context-free Grammars and Languages [Note 2]
- Note on Turing Machines [Note 3] [Note 4]
Classes (by Dr. Nilanjan Datta):
- An Introduction to Pushdown Automata (PDA), Some Examples [Class 1]
- Examples of PDA, Instantaneous Description (ID) of a PDA, Correctness of a PDA via ID, Acceptance by Empty stack, and Equivalence of the two notions: Acceptance by final state and empty stack. [Class 2]
- From Context-free Grammars to PDA, Closure Properties of Context-free Languages. [Class 3]
- From PDA to Context-free Grammars, Membership problem: CYK Algorithm, Some interesting problems related to PDA. [Class 4]