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 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 - End-Sem Exam

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.

Evaluation:

There will be up to four quizzes. The quizzes carry a weightage of 40%. The mid-semester exam and the end-semester 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. 


Schedule

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 1-2-3 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 47-54 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 1-3 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 Kleene-star)

 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

  • Quotients/Residuals.

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 product-automaton with q' \in F'\}.


  • Rational languages / sets

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 - intersection-nonemptiness - inclusion/containment - equivalence.

Additional reading: Section 3.2 and Section 4.3 of HopcroftMotwaniUllman, and related exercises.
26/08/2017 QUIZ 1 Lectures 1-7
29/08/2017 Lecture 8 Pumping lemma - proving non-regularity 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 Myhill-Nerode theorem. 

Additional reading: Lecture 16 of Kozen (Defn 16.1 onwards), Section 4.6 of this lecture notes by Jean-Eric Pin (He uses \cdot for \delta and q_{\_} for q_0 ).

Problems 1.51 and 1.52 of Sipser.
02/09/2017 Lecture 10 Myhill-Nerode 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 1-10
  • Problem Set 4
  • Last year's Quiz 2
  • Last year's Mid-sem Exam
    • 07/09/2017 Optional Lecture
    12/09/2017 Lecture 11 Context-free 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 1-10
    15/09/2017 Lecture 12 Left-most 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 equi-powerful.

    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 Mid-semester exam Lectures 1-14
    03/10/2017 Lecture 15 Closure properties of context-free languages:
    closed under union, concatenation, intersection with regular languages, Kleene star, homomorphism, inverse homomorphism, substitutions, reversals.
    not closed under intersection, complementation.

    Algorithms for non-emptiness, membership (CYK)

    Linear context-free 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 non-deterministic 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

    Notes
    05/10/2017 Lecture 17

    Variants of Turing Machines

    Classes of languages:

    • recursively enumerable languages (Turing recognizable)
    • co-recursively enumerable languages 
    •  recursive languages

    Recursive iff r.e. and co-r.e.

    decidable problems, semi-decidable problems.

    Turing recognizable iff there is an enumerator

    there exists non-r.e. languages (by counting argument)

    Universal Turing Machine

    3.2 of Sipser, Lectures 29,30 of Kozen, 8.3,8.4 of HopcroftMotwaniUllman

    Notes
    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

    Notes
    09/10/2017 Lecture 19 Reductions - more undecidable problems - non-emptiness, universality, inclusion of Turing recognizable languages.

    Rice's theorem - proof.

    		Lecture 32,33,34 of Kozen

    Notes Problem Set 6

    10/10/2017 Lecture 20 Rice's theorem continued

    Other Turing powerful models : 2-stack machines, 3 counter machines, 2 counter machines (aka Minsky machines)

    		Lecture 34 of Kozen, Section 8.5 of HopcroftMotwaniUllman

    Notes Problem Set 6

    11/10/2017 Lecture 21

    Other Turing powerful models : 2-stack 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

    Notes Problem Set 6

    12/10/2017 Lecture 22

    Post's Correspondence Problem, Modified Post's Correspondence Problem, reduction from membership problem for turing machines

    Undecidable problems on context-free 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

    Notes Problem Set 6 Problem Set 7

    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 End-semester Exam Last year's End-sem exam