Final exam on Monday 25/11/2019 at 09:30 in Seminar Hall

This is a mandatory course for the following batches:

  1. BSc Mathematics and Computer Science (II year)
  2. MSc Computer Science (I year)
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 LH804 on Mondays and Tuesdays from 9:10 to 10:25.

Weekly problem set will be given on Tuesday. The students are expected to submit the answers to the TAs by Thursday. Each problem set will have 4 problems. The solution to each problem must be written in a separate sheet.

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, as well as all the practice problems given in the reference books. Here are the links to the previous years' course webpages: 2018 2017 2013

Evaluation:

There will be up to three quizzes in addition to the smid-semester exam and the end-semester exam. The weightage for the final grading will be as follows: (The weightage is subject to change)

Exam Date Weightage
Quiz 1 3- Sep - 2019 10 %
Mid semester exam 23 - Sep - 2019, 9:30 am 30 %
Quiz 2 21 - Oct - 2019, 9:10 am, LH 804 10 %
Quiz 3 12 - Nov - 2019, 9:10 am, LH 804 10 %
End semester exam 25 - Nov - 2019, 9:30 am, Seminar Hall 40 %

Instructor:

C. Aiswarya

Teaching Assistants:

The teaching assistants (listed below) will give you the weekly problem sheets. You should submit your answers to them. Feel free to talk to the TAs if you have questions, or want feedback on your solutions, for the practice problems or even other exercises on the topics covered in the course. 

Please find below the approximate hours when students can find the TAs:
Ekanshdeep : after 10 pm, Computer lab / F-12
Asif : After 9:30 pm, F-06
Adwitee : Weekdays, mostly before lunch, FL-2
Ankita : Weekdays 10 pm to midnight, Computer Lab / T-02. Weekends by appointment.


Schedule

Date Descr Topics covered Resources/materials
5/8/2019 Lecture 1 Alphabet - strings - langauges - decision problems - Finite State Automata - examples (contains "ab", ends with "abbab", even binary number, binary numbers that are multiples of three) - runs - acceptance - language of an automata Additional reading: Chapter 1, 2.1 and 2.2 of HopcroftUllman, Lectures 1-2-3 of Kozen, Chapters 0 and 1.1 of Sipser.
6/8/2019 Lecture 2 NFA - runs - extended transition relations - language of an NFA - examples - subset construction - correctness of susbet 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-58 of Sipser
6/8/2019 Problem Set 1 Submit on or before Thursday 8/8/2019 to the TAs for feedback. Answer each question in a separate sheet. Non complying submissions will not be read by the TAs
Problem Set 1
Feedback
13/8/2019 Lecture 3 ε-NFA  -- ε-NFA have the same recognizing power as NFA -- ε elimination -- correctness argument 
Additional reading: Section 2.5 of HopcroftMotwaniUllman
13/8/2019 Problem Set 2 Submit on or before Thursday 15/8/2019 to the TAs for feedback. Answer each question in a separate sheet. Non complying submissions will not be read by the TAs
Problem Set 2
Feedback
19/8/2019 Lecture 4 Closure properties of recognizable languages -- under boolean operations (union, intersection, complementation), concatenation, iteration (aka star, or Kleene-star) -- Cartesian product of automata - Cartesian product construction. Class of rational languages - Rational languages are recognizable. Rational expressions.
Additional reading: Section 1.2 of Sipser, Section 4.2 of HopcroftMotwaniUllman
20/8/2019 Lecture 5 Kleene's theorem - proof -- closure under homomorphism and inverse homomorphism
Additional reading: Section 1.3 of Sipser, Section 3 and 4.2 of HopcroftMotwaniUllman
20/8/2019 Problem Set 3 Submit on or before Thursday 22/8/2019 to the TAs for feedback. Answer each question in a separate sheet. Non complying submissions will not be read by the TAs
Problem Set 3
Feedback
26/8/2019 Lecture 6 Closure properties continued - closure under quotients/ residuals.
Existence of non-recognizable languages by counting argument.
Number of residuals is finite if L is recognizable. Technique to prove non-recognizability: show that there is an infinite number of residulas -- or, equivalently -- infinite set of pair-wise distinguishable words.
Distinguishing suffix for a pair of words
Additional reading: Problems 1.51 and 1.52 of Sipser.
27/8/2019 Lecture 7 Myhill-Nerode theorem: Number of residuals is finite iff L is recognizable. Constructing the Nerode automaton of a regular language. The Nerode automaton is the minimal DFA. Algorithm for membership in a recognizable language. Algorithm for emptiness checking. Pumping lemma.
27/8/2019 Problem Set 4 Submit on or before Thursday 29/8/2019 to the TAs for feedback. Answer each question in a separate sheet. Non complying submissions will not be read by the TAs
Problem Set 4
Feedback
3/9/2019 Quiz 1
9/9/2019 Lecture 8 Pumping Lemma. The relation ≡L is a congruence. The relation ≡A is a congruence. The relation ≡A refines ≡L(A). Minimizing a DFA by partition refinement algorithm. Additional reading: Lectures 13, 14, 15, 16 of Kozen, Section 4.4 of HopcroftMotwaniUllman
10/9/2019 Lecture 10 Minimizing a DFA by partition refinement algorithm. Example. 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
10/9/2019 Problem set 5 Submit on or before Thursday 12/9/2019 to the TAs for feedback. Answer each question in a separate sheet. Non complying submissions will not be read by the TAs
Problem Set 5
Feedback
16/9/2019 Lecture 11 Context-free grammars - examples - derivation - sentence - sentential form - Left-most derivations - right most derivations - parse trees - ambiguity - inherently ambiguous languages
Eliminating epsilon productions and unit productions - Chomsky Normal Form 		Additional reading: Section 5.1, 5.2 and 5.4 of HopcroftMotwaniUllman, Section 2.1 of Sipser, Lectures 19, 20, 21 of Kozen
17/9/2019 Lecture 12 Chomsky Normal Form, Pumping lemma for context-free languages, examples, regular languages are context free, some closure properties Additional reading: Section 7.2 of HopcroftMotwaniUllman, Section 2.3 of Sipser, Lectures 22 of Kozen
17/9/2019 Problem Set 6 Submit on or before Thursday 19/9/2019 to the TAs for feedback. Answer each question in a separate sheet. Non complying submissions will not be read by the TAs
Problem Set 6
30/9/2019 Lecture 13 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
1/10/2019 Lecture 14 from CFG to PDA. from PDA to CFG 6.3 of HopcroftMotwaniUllman,Lecture 24, 25 of Kozen
1/10/2019 Problem Set 7 Submit on or before Thursday 03/10/2019 to the TAs for feedback. Answer each question in a separate sheet. Non complying submissions will not be read by the TAs
Problem Set 7
7/10/2019 Lecture 15 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
15/10/2019 Lecture 16 Deterministic Turing machines, examples, language of a Turing machine - recursively enumerable languages - semi-decidable problems, total Turing Machine - recursive languages - decidable problems
Lectures 28, 29 of Kozen, 3.1 of Sipser
15/10/2019 Problem set 8 Submit on or before Thursday 17/10/2019 to the TAs for feedback. Answer each question in a separate sheet. Non complying submissions will not be read by the TAs
Problem Set 8
22/10/2019 Lecture 17 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
22/10/2019 Problem Set 9 Submit on or before Thursday 24/10/2019 to the TAs for feedback. Answer each question in a separate sheet. Non complying submissions will not be read by the TAs
Problem Set 9
28/10/2019 Lecture 18 variants - Turings machines with bi-infinite tape, k tapes, k heads, Non-determinsitc Turing machines, 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. There exists languages that are not recursively enumerable. Counting argument. Cantor's diagonalization argument
 Lectures 30,31 of Kozen, 3.2 of Sipser
29/10/2019 Lecture 19 Universal turing machine -- a Turing Machine for the language membership problem of turing machines. Membership problem is recursively enumerable. It is not recrsive. Proof by contradiction via Cantor's diagonalization argument to arrive. Co-recursively enumerable lanaguges. A language is recurive iff it is r.e. and co-r.e.
Exercise: Prove that Halting problem is not co-r.e. by diagonalisation. 		Lectures 30,31 of Kozen, 3.2 of Sipser
29/10/2019 Problem Set 10 Submit on or before Thursday 31/10/2019 to the TAs for feedback. Answer each question in a separate sheet. Non complying submissions will not be read by the TAs
Problem Set 10
04/11/2019 Lecture 20 Reductions. Epsilon-membership, and Non-emptiness are r.e. but not co-r.e. What about universality? Lectures 32, 33 of Kozen
05/11/2019 Lecture 21 More Reductions. Universality is not re, and not co-re. Finiteness is not re, not co-re. Lectures 32, 33 of Kozen
05/11/2019 Problem Set 11 Submit on or before Thursday 7/11/2019 to the TAs for feedback. Answer each question in a separate sheet. Non complying submissions will not be read by the TAs
Problem Set 11
11/11/2019 Lecture 22 Rice's theorem. Proof. Lectures 34 of Kozen
18/11/2019 Lecture 23 Turing powerful models of computations.. 2-stack machines, k-counter machines - 4 counter machines can simulate 2-stack machines - 3 counter machines can simulate 2 stack machines - 2 counter machines can simulate 3 counter machines (Minsky machines) 8.5 of HopcroftMotwaniUllman, Lecture 30 of Kozen
19/11/2019 Lecture 24 Turing powerful models of computations cntd .. Queue machines.
Undecidability of universality of context free languages.. (reductions via encoding valid computation histories of a turing machine)
Post's Correspondence Problem
Undecidability of universality of CFL: Lecture 35 of Kozen

PCP : 9.5 of HopcroftMotwaniUllman, 5.2 of Sipser
20/11/2019 Problem Set 12 Submit on or before Friday 22/11/2019 to the TAs for feedback. Answer each question in a separate sheet. Non complying submissions will not be read by the TAs
Problem Set 12