This is a mandatory course for the following batches:
Schedule
The lectures will take place in the Seminar Hall on Tuesdays and Thursdays from 10:30 to 11:55. Quizzes and compensating lectures will be in the Seminar Hall on Saturdays from 10:30 to 11:55. Tutorial sessions will be kept once a week (when? will be decided on the fly), and the practice problems will be distributed beforehand.
17/10/2017, 10:30 am  QUIZ 3
21/10/2017  EndSem Exam
References:
Evaluation:
There will be up to four quizzes. The quizzes carry a weightage of 40%. The midsemester exam and the endsemester exam carry a weightage of 30% 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.
Date  Descr  Topics covered  Resources/materials 

8/8/2017  Lecture 1  Alphabet  strings  langauges  problems  Determinsitic Finite State Automata  examples (contains "ab", even length, even binary numbers)  Problem Set 1 Additional reading: Chapter 1, 2.1 and 2.2 of HopcroftUllman, Lectures 123 of Kozen, Chapters 0 and 1.1 of Sipser. 
10/8/2017  Lecture 2  DFA  runs  extended transition function  language of a DFA  NFA  runs  extended transition relations  language of an NFA  examples (second last letter is an 'a')
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: Example 2.9 of HopcroftMotwaniUllman, Sections 2.3.1, 2.3.2, 2.3.3, 2.3.4 of HopcroftMotwaniUllman, pages 4754 of Sipser 
12/8/2017  Lecture 3  DFA and NFA have the same recognizing power. Subset construction.  Additional reading: Lecture 5, Lecture 6 of Kozen, Section 2.3 of HopcroftUllman 
16/8/2017  Tutorial 1  Lectures 13 
Problem Set 1 Problem Set 2 
17/8/2017  Lecture 4  εNFA  εNFA have the same recognizing power as NFA  ε elimination  correctness argument Closure properties of regular languages  under boolean operations (union, intersection, complementation), concatenation, iteration (aka star, or Kleenestar) 
Section 2.5 of HopcroftUllman, Lecture 6 of Kozen, Section 1.2 of Sipser
Problem Set 3 
19/8/2017 10:30  Lecture 5  Cartesian product of automata  the class of regular languages are closed under homomorphism, inverse homomorphism and reverse  constructions.  Additional reading: Section 4.2 of HopcroftMotwaniUllman 
21/8/2017  Tutorial 2  Problem Set 3  
22/8/2017  Lecture 6 
Let L be regular and L_1 an arbitrary language (need not be computable). Then L_1^{1} L is regular. Let A=(Q,\Sigma, \delta, q_0, F) be a DFA for L. Then A' = (Q, \Sigma, \delta, Q_0, F) is an NFA for L_1^{1}L where Q_0 = \{ \hat \delta(q_0,w) \mid w \in L_1 \} . Q_0 \subseteq Q exists, but we may not be able to compute it. If L_1 is regular then we can effectively compute Q_0. Suppose L_1 is recognized by A' = (Q',\Sigma,\delta',q_0',F') . Consider the states/transitions of the cartesian product : ( Q' \times Q, \Sigma, \delta'', \dots ) . Trim this automaton to contain only states that are reachable from (q_0',q_0). Then Q_0 = \{ q \mid (q',q) is a state of the trimmed productautomaton with q' \in F'\}.
Rational expressions. All rational languages are recognizable (by structural induction on the rational expression). All recognizable languages are rational. State elimination algorithm (to be continued in the next lecture) 
Additional Reading: Chapter 3 of HopcroftMotwaniUllman, Try exercises 4.2.2  4.2.5 of HopcroftMotwaniUllman. Section 1.3 of Sipser 
22/8/2017  Lecture 7  Kleene's theorem.  conversion from automata to regular expression  state elimination algorithm. Algorithmic questions on finite representations of regular languages (automata/rational expressions)  membership  nonemptiness  universality  finiteness  intersectionnonemptiness  inclusion/containment  equivalence. 
Additional reading: Section 3.2 and Section 4.3 of HopcroftMotwaniUllman, and related exercises. 
26/08/2017  QUIZ 1  Lectures 17  
29/08/2017  Lecture 8  Pumping lemma  proving nonregularity of langauges distinguishing right contexts for strings 
Additional reading: Lectures 11 and 12 of Kozen, Section 4.1 of HopcroftMotwaniUllman 
31/08/2017  Lecture 9  Characterisation of regular languages : L is regular iff it has finitely many left quotients /residuals. Using the characterisation by finite residuals to show that a language is not regular. Defining the right congruence in terms of distinguishing right contexts, and alternative statement of the MyhillNerode theorem. 
Additional reading: Lecture 16 of Kozen (Defn 16.1 onwards), Section 4.6 of this lecture notes by JeanEric Pin (He uses \cdot for \delta and q_{\_} for q_0 ). Problems 1.51 and 1.52 of Sipser. 
02/09/2017  Lecture 10  MyhillNerode theorem  uniqueness of the minimal DFA  \equiv_A refines \equiv_L  construction of the Nerode automata  DFA state minimization algorithm via partition refinement.  Additional reading: Lectures 13,14,15,16 of Kozen, Section 4.4 of HopcroftMotwaniUllman 
05/09/2017  Optional Lecture  
Tutorials  Lectures 110 


07/09/2017  Optional Lecture  
12/09/2017  Lecture 11  Contextfree grammars  examples  derivation  sentence  sentential form  linear grammars  right linear iff regular.  Section 5.1 of HopcroftMotwaniUllman, Section 2.1 of Sipser, Lectures 19,20 of Kozen Notes 
14/09/2017  QUIZ 2  Lectures 110  
15/09/2017  Lecture 12  Leftmost derivations  right most derivations  parse trees  ambiguity  inherently ambiguous  normal forms  epsilon elimination  Chomsky normal form  Pumping Lemma for CFL 
Section 2.1 of Sipser, Lectures 21,22 of Kozen, Section 5.2, 5.4, 7.1, 7.2 of HopcroftMotwaniUllman Notes Problem Set 5 
20/09/2017  Lecture 13  Pumping lemma for context free languages  examples  greibach normal form Pushdown automata  examples 
Section 7.2, 6.1 of HopcroftMotwaniUllman, Lecture 22,23 of Kozen, Sections 2.1,2.3,2.2 of Sipser Notes Problem Set 5 
21/09/2017  Lecture 14  pushdown automata  acceptance by final states  acceptance by empty stack  both acceptance mechanisms are equipowerful. 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 
Lecture 23, E, 24, 25 of Kozen, Sections 6.2, 6.3 of HopcroftMotwaniUllman Notes Problem Set 5 
22/09/2017  Tutorial  Problem Set 5  
27/09/2017  Midsemester exam  Lectures 114  
03/10/2017  Lecture 15  Closure properties of contextfree languages: closed under union, concatenation, intersection with regular languages, Kleene star, homomorphism, inverse homomorphism, substitutions, reversals. not closed under intersection, complementation.
Algorithms for nonemptiness, membership (CYK) Linear contextfree lnaguages, DPDA, unambiguous grammars : strictly less powerful than CFG 
References: 7.3,7.4 of HopcroftMotwaniUllman Additional reading: 6.4 of HopcroftMotwaniUllman Notes 
04/10/2017  Lecture 16 
Turing machines  examples  deterministic turing machine can simulate nondeterministic turing machines  When asked to describe a turing machine, you may give descriptions similar to the examples in Ch 3 of Sipser. 
Ch 3 of Sipser, 8.4.4 of HopcroftMotwaniUllman 
05/10/2017  Lecture 17  Variants of Turing Machines Classes of languages:
Recursive iff r.e. and cor.e. decidable problems, semidecidable problems. Turing recognizable iff there is an enumerator there exists nonr.e. languages (by counting argument) Universal Turing Machine 
3.2 of Sipser, Lectures 29,30 of Kozen, 8.3,8.4 of HopcroftMotwaniUllman 
06/10/2017  Lecture 18 
Universal Turing Machines  Proof that there exists languages that are r.e. but not rec. Halting Problem (HP)  diagonalization. HW: prove that membership problem (MP) is not rec by diagonalization. Proof that MP is not recursive by reduction from HP. 
Lecture 31 of Kozen 
09/10/2017  Lecture 19 
Reductions  more undecidable problems  nonemptiness, universality, inclusion of Turing recognizable languages.
Rice's theorem  proof. 
Lecture 32,33,34 of Kozen 
10/10/2017  Lecture 20 
Rice's theorem continued
Other Turing powerful models : 2stack machines, 3 counter machines, 2 counter machines (aka Minsky machines) 
Lecture 34 of Kozen, Section 8.5 of HopcroftMotwaniUllman 
11/10/2017  Lecture 21 
Other Turing powerful models : 2stack machines, 3 counter machines, 2 counter machines (aka Minsky machines), Queue Machines Post's Correspondence Problem, Modified Post's Correspondence Problem, reduction from membership problem for turing machines (to be cntd..) 
Section 9.4 of HopcroftMotwaniUllman, 5.2 of Sipser 
12/10/2017  Lecture 22 
Post's Correspondence Problem, Modified Post's Correspondence Problem, reduction from membership problem for turing machines Undecidable problems on contextfree langauges.  Ambiguity checking of grammars, universality checking 
Section 9.4 of HopcroftMotwaniUllman, 5.2 of Sipser 9.5.2 of HopcroftMotwaniUllman, Theorem 5.13 and proof of Sipser, Lecture 35 of Kozen: a reduction from Halting problem to Universality of PDA 
13/10/2017  Tutorials  Problem Set 6  
16/10/2017  Tutorials  Problem Set 7  
17/10/2017  QUIZ 3  Last year's Quiz 4  
21/10/2017  Endsemester Exam  Last year's Endsem exam 