COL 352 Introduction to Automata and Theory of Computation

Staff

Instructor: Nikhil Balaji (nbalaji)

TAs: Prashant Agrawal (csz188011), Nikhil Ayyadevara (cs1170330), Indrajit Banerjee (csy207569)

Vijay Bhardwaj (mcs202476), Shivansh Juyal (mcs202471), Bikram Mondal (mcs212127)


Slot: H (Mon, Wed - 11:00 - 12:00, Thu: 12:00 - 13:00)


Prerequisites


COL202 or MTL180 or an equivalent course. Specifically, the following topics:

  • Proof techniques - construction, contradiction, induction, counting techniques.

  • Sets and set operations, relations

  • Functions -- injections, surjections, and bijections; cardinality

  • Countability and uncountability, diagonalization

  • Equivalence relations, partial orders

If you haven't done either but would like to attend the course, email me.


Content (tentative)


  • Finite state machines and finite automata, nondeterminism, regular languages and their properties, regular expressions, pumping lemma for regular languages, Myhill-Nerode theorem, minimal automata

  • Grammars, ambiguity, context-free languages and their properties, pumping lemma for context-free languages, pushdown automata

  • Turing machines, deciders, multi-tape and non-deterministic Turing machines, Turing-recognizability and decidability, enumerators

  • Undecidability and un-recognizability, mapping reductions, Rice's theorem, connections to problems in mathematical logic

  • Other topics (Streaming algorithms, Kolmogorov complexity, Weighted automata, etc..)


Textbooks

  • Introduction to the Theory of Computation by Michael Sipser

  • Elements of the Theory of Computation by Harry Lewis and Christos Papadimitriou

  • Automata and Computability by Dexter Kozen



Grading (tentative)



Homeworks - 30%

Quizzes - 30%

Major exam - 40%



30% marks necessary for a passing grade.



Useful Platforms



Lecture Schedule


  1. Jan 3: Intro to the course, logistics, motivation. Reading: Sipser Chapter 0

  2. Jan 5, 6: Recap, languages, decision problems, finite state machines, DFA examples, formal definitions. Reading: Sipser section 1.1, Kozen lectures 2,3.

  3. Jan 10,12,13: NFA examples, formal definition, closure properties of regular languages, Subset construction, epsilon-NFAs. Reading: Sipser section 1.2.

  4. Jan 17,19,20: Exponential lower bound for subset construction, Regular expressions, Equivalence with DFA, NFA, non-regular languages.Reading: Sipser section 1.3, Kozen lectures 7-9.

  5. Jan 24, 27, 29: Non-regular languages, Pumping lemma and its applications, Myhill-Nerode relations. Reading: Kozen lectures 11-12, 15. Sipser section 1.4.

  6. Jan 31, Feb 2, 3: Myhill-Nerode theorem, DFA minimization, 2DFAs intro. Reading: Kozen lectures 13, 14, 16, 17.

  7. Feb 7, 9, 10: 2DFAs and regular sets, streaming algorithms, discussion of other related models, Pushdown Automata. Reading: Kozen lectures 17, 18, lecture notes on streaming algorithms by Luca Trevisan.

  8. Feb 14-17: Minor week.

  9. Feb 21, 23, 24: Pushdown Automata- definition, examples; Context-free Grammars -definitions, examples, ambiguity, parse trees, CFG to PDA. Reading: Sipser section 2.1, 2.2, Kozen lectures 19, 21, 23

  10. Feb 26 - Mar 1: Break.

  11. Mar 2, 3: PDA to CFG, Pumping lemma for CFGs, Pumping lemma examples. Reading: Sipser section 2.2, 2.3, Kozen chapters 22,25

  12. Mar 7, 9, 10: Turing machines and computability - definition, examples, variants, Church-Turing Thesis. Reading: Sipser chapter 3, Kozen chapters 28, 29, 30.

  13. Mar 14, 16, 17: Undecidability, Reductions, examples of undecidable problems, LBA, PCP. Reading: Sipser chapter 4, parts of 5, Kozen chapters 31, 32, 33.

  14. Mar 21, 23, 24: Undecidability of PCP, Rice's theorem and applications, Advanced topics - Recursion theorem. Reading: Sipser chapter 5, section 6.1, Kozen chapters 34.

  15. Mar 28, 30, 31: Kolmogorov Complexity, Turing reduction/degrees, Efficient computation. Reading: Sipser sections 6.2, 6.3, 7.2