This is a mandatory course for the following batches:

  1. BSc Mathematics and Computer Science (II year)
  2. MSc Computer Science (I year)
  3. MSc Applications of Mathematics (Analytics) (II year)
  4. Pre-PhD in CS / PhD students in CS doing course work
If any other student wants to credit/audit this course, she/he needs to get a prior approval from the teacher.

Schedule

The lectures will take place in the Seminar Hall on Tuesdays and Thursdays from 9:10 to 10:25. Tutorial sessions will be kept once a week (when?where? will be decided on the fly), and the practice problems will be distributed beforehand.

References:

  1. Introduction to Automata Theory, Languages and Computation (1st edition) by John E. Hopcroft and Jeffrey D. Ullman, Addison-Wesley, 1979.
  2. Introduction to Automata Theory, Languages and Computation (3rd edition) by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Pearson Education, 2007.
  3. Automata and Computability by Dexter Kozen, Springer-Verlag, 1997.
  4. Introduction to the Theory of Computation by Michael Sipser, Thomson Brooks/Cole, 1997.
The course will follow the same structure and style as in the previous years. Students are encouraged to do the problem sheets/tutorials of previous years. Here are the links to the previous years' course webpages: 2017 2013

Evaluation:

There will be up to two quizzes. The quizzes carry a weightage of 20%. The mid-semester exam and the end-semester exam carry a weightage of 40% each. (The weightage is subject to change)

Teaching Assistants:

The teaching assistants (listed below) will give you practice problems and conduct tutorials. The students may talk to them if they have questions, or want feedback on their solutions, for the practice problems or even other exercises on the topics covered in the course. 


Problem Set 1    Problem Set 2    Problem Set 3    Problem Set 4    Bonus Problem Set    Problem Set 5    Problem Set 6    Problem Set 7    Problem Set 8

Schedule

Date Descr Topics covered Resources/materials
7/8/2018 Lecture 1 Alphabet - strings - langauges - problems - Determinsitic Finite State Automata - examples (contains "ab", even length) - runs - extended transition function - language of a DFA Additional reading: Chapter 1, 2.1 and 2.2 of HopcroftUllman, Lectures 1-2-3 of Kozen, Chapters 0 and 1.1 of Sipser.
9/8/2018 Lecture 2 NFA - runs - extended transition relations - language of an NFA - examples - subset construction

NB: The definition of NFA used in the class is different from that in the text books. 1) We allow multiple initial states. 2) The transitions are seen as a relation instead of a function.

Additional reading: Lecture 5, Lecture 6 of Kozen, Example 2.9 of HopcroftMotwaniUllman, Sections 2.3 of HopcroftMotwaniUllman, pages 47-54 of Sipser,
9/8/2018 Problem Set 1 Problem Set 1
14/8/2018 Lecture 3 correctness of susbet construction -- ε-NFA  -- ε-NFA have the same recognizing power as NFA -- ε elimination -- correctness argument 
Additional reading: Lecture 5, Lecture 6 of Kozen, Section 2.3 and 2.5 of HopcroftMotwaniUllman
16/8/2018 Lecture 4 Closure properties of regular languages -- under boolean operations (union, intersection, complementation), concatenation, iteration (aka star, or Kleene-star) -- Cartesian product of automata
Additional reading: Section 1.2 of Sipser, Section 4.2 of HopcroftMotwaniUllman
16/8/2018 Problem Set 2 Problem Set 2
20/8/2018 Tutorial 1
21/8/2018 Lecture 5 Rational languages -- Rational Expressions -- Kleene's theorem
Additional reading: Section 1.3 of Sipser, Section 3 of HopcroftMotwaniUllman
23/8/2018 Lecture 6 Closure properties continued: reverse, homomorphism, inverse homomorphism, quotients/residuals
Section 4.2 of HopcroftMotwaniUllman, Lecture 10 of Kozen
24/8/2018 Problem Set 3 Problem Set 3
27/8/2018 Tutorial 2, LH6
28/8/2018 Lecture 7 Pumping lemma. Proving non-regularity. distinguishing suffix for a pair of words. Infinite set of pair-wise distinguishable words to prove non-regularity. Additional reading: Lectures 11 and 12 of Kozen, Section 4.1 of HopcroftMotwaniUllman
30/8/2018 Lecture 8 Proving non-regularity. Infinite set of pair-wise distinguishable words -- or, equivalently -- Infinite set of residuals. Constructing the Nerode automaton of a language. Myhill-Nerode theorem: A language is regular if and only if it has finitely many residuals. Additional reading: Problems 1.51 and 1.52 of Sipser. CHalpter III, Section 4.6 of this lecture notes by Jean-Eric Pin (He uses ‧ for δ and q_ for q0 ).
1/9/2018 Tutorial 3
1/9/2018 Problem Set 4 Problem Set 4
4/9/2018 Lecture 9 Myhill-Nerode theorem. The relation ≡L is a congruence. The relation ≡A is a congruence. The relation ≡A refines ≡L(A). Nerode automaton for L is the smallest DFA for L (if L is regular). Minimizing a DFA by partition refinement algorithm. Additional reading: Lectures 13, 14, 15, 16 of Kozen, Section 4.4 of HopcroftMotwaniUllman
5/9/2018 QUIZ 1 Seminar Hall, 17:00
6/9/2018 Lecture 10 Minimizing a DFA by partition refinement algorithm. Algorithmic questions on finite representations of regular languages (automata/rational expressions) - membership - nonemptiness - universality - finiteness - intersection-nonemptiness - inclusion/containment - equivalence. Additional reading: Section 4.3 and 4.4 of HopcroftMotwaniUllman
8/9/2018 Bonus Problem Set Bonus Problem Set
11/9/2018 Lecture 11 Context-free grammars - examples - derivation - sentence - sentential form - Left-most derivations - right most derivations - parse trees - ambiguity - inherently ambiguous languages Additional reading: Section 5.1, 5.2 and 5.4 of HopcroftMotwaniUllman, Section 2.1 of Sipser, Lectures 19,20 of Kozen
17/9/2018 Problem Set 5 Problem Set 5
19/9/2018 Lecture 12 Eliminating epsilon productions and unit productions - Chomsky Normal Form - Pumping Lemma for context-free languages Additional reading: Lectures 21, 22 of Kozen, Section 2.1 , 2.3 of Sipser, 7.1,7.2 of HopcroftMotwaniUllman
19/8/2018 Problem Set 6 Problem Set 6
24/9/2018 Mid Semester Exam
15/10/2018 Lecture 13 Greibach normal form -Pushdown automata - examples - acceptance by final states - acceptance by empty stack - both acceptance mechanisms are equi-powerful 6.1,6.2 of HopcroftMotwaniUllman, Lecture 23, E of Kozen,
16/10/2018 Lecture 14 from CFG to PDA. We construct a PDA with only one state!. Notice that if the CFG is in Greibach normal form, we get a PDA without epsilon transitions.
from PDA to CFG		 6.3 of HopcroftMotwaniUllman,Lecture 24, 25 of Kozen (different construction)
23/10/2018 Lecture 15 from CFG to PDA and back.
closure properties of CFLs. closed under union. not closed under intersection and complementation.
24/10/2018 Lecture 16 closure properties of CFLs.
not closed under intersection and complementation.
closed under union, concatenation, Kleene star, homomorphism, inverse homomorphism, context-free substitutions, reverse, intersection with regular language		 Section 7.3 of HopcroftMotwaniUllman
25/10/2018 Lecture 17 Algorithmic questions on context-free lanagues.
Algorithm for membership: (CKY) algorithm
Algorithm for non-emptiness.

No algorithm exists for universality testing, equivalence testing, ambiguity testing, intersection non-emptiness checking etc.. (without proof)		 Section 7.4 of HopcroftMotwaniUllman, Lecture 27 of Kozen
25/10/2018 Problem Set 7 Problem Set 7
30/10/2018 Lecture 18 Deterministic Turing machines, examples, configuration, language of a Turing machine, recursively enumerable languages, total Turing Machine, recursive languages
Lectures 28,29 of Kozen, 3.1 of Sipser
31/10/2018 Lecture 19 Non-determinsitc Turing machines, Turings machines with bi-infinite tape, k tapes, k heads etc. Simulation of the variants by standard turing machine. Non-determistic turing machines have the same power as deterministic turing machines. Universal turing machine -- a Turing Machine for the language membership problem of turing machines.
Lectures 30,31 of Kozen, 3.2 of Sipser
1/11/2018 Lecture 20 Enumeration Machines. Universal turing machine -- a Turing Machine for the language membership problem of turing machines. There are languages that are not recursively enumerable. Proof by counting argument. There are recursively enumerable languages that are not recursive. Proof by diagonalization.
 Lectures 30,31 of Kozen, 4.1, 4.2 of Sipser
1/11/2018 Lecture 21 Membership problem of Turing machines. It is recursively enumerable (aka semi-decidable) (via a universal turing machine) but it is not recursive. Proof by diagonalization. Hence the membership problem is not co-r.e.
Exercise: Prove that Halting problem is undecidable by diagonalization. 		Lectures 30,31 of Kozen, 4.2 of Sipser
1/11/2018 Problem Set 8 Problem Set 8
13/11/2018 Lecture 22 Reductions. more undecidable problems . Epsilon-membership, non-emptiness Lectures 32,33 of Kozen
15/11/2018 Lecture 23 Reductions. more undecidable problems. Statement of Rice's theorem. Lectures 32,33 of Kozen
16/11/2018 Lecture 24 Reductions. Rice's theorem. Proof Lectures 34 of Kozen
20/11/2018 Lecture 25 Turing powerful models of computations.. 2-stack machines, k-counter machines - 3 counter machines - 2 counter machines (Minsky machines) - More undecidable problems: Post's Correspondence Problem - ambiguity checking of CFGs 5.2 of Sipser, 8.5, 9.4, 9.5.2 of HopcroftMotwaniUllman
22/11/2018 Lecture 26 Undecidability of universality checking of context-free languages. Lecture 35 of Kozen