COL 352 Introduction to Automata and Theory of Computation

Staff

Instructor:  Nikhil Balaji (nbalaji)

TAs:   Sourav Bansal (cs5180421), Suraj Patni (csy217550), Sanaa Siddiqui (csy227516), 

            Surbhi Rajput (csy227519), Harsh Singh Chauhan (mcs222052), Badrinath Padmanabhan (csz228626)

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

Venue: LH 318

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

• Automata and Computability by Dexter Kozen

• Introduction to the Theory of Computation by Michael Sipser

Grading (tentative)

Quizzes                          - 30%   

Minors - 35%

Major exam                  - 35%

30% marks necessary for a passing grade. 

Useful Platforms

• Microsoft Teams for course announcements (check the 'Lectures' channel)

• Moodle, Piazza for announcements and discussions

• Gradescope for exam feedback

Lecture Schedule

1. Jan 4: Intro to the course, logistics, motivation; Modelling computation: languages, machines, etc. Reading: Sipser Chapter 0, Kozen Chapter 1, 2.

2. Jan 5: Deterministic Finite Automata:  Examples, Definitions. Existence of non-regular languages. Reading: Sipser Chapter 1, Kozen Chapter 2,3.

3. Jan 9: DFA, Regular languages - Closure under union, complement, intersection. Nondeterminism. Reading: Kozen Chapter 3, 4

4. Jan 11: NFA: Examples, Definitions, Conversion to DFA: Subset construction. Reading: Kozen Chapter 5

5. Jan 12: NFA: Subset construction proof, worst case complexity of subset construction. Reading: Kozen Chapter 6

6. Jan 16: NFA: Epsilon transitions, closure of regular languages under concatenation, Kleene Star. Reading: Sipser Chapter 1.2 

7. Jan 18:  No class

8. Jan 19: Pattern matching and Regular expressions. Regular expressions to NFA conversion. Reading: Kozen Chapters 7, 8

9. Jan 23: No class

10. Jan 25: Quiz 1

11. Jan 26: Holiday (Republic day)

12. Jan 28 (Saturday): DFA to regular expressions conversion, limitations of DFA - a few non-regular languages. Reading: Kozen Chapters 9, 11

13.  Jan 30: Pumping Lemma: Proof, Examples. Reading: Kozen Chapters 11.

14. Feb 1: Using Pumping Lemma, Homomorphims, Reading: Kozen Chapters 10, 12

15. Feb 2: A refined pumping lemma, a few tricks to show (non)-regularity, Ultimate periodicity and unary languages. Reading: Kozen Chapters 10, 11 

16. Feb 6-9: Minor week 

17. Feb 13: No class

18. Feb 16: DFA minimization, Quotient construction, Table-filling algorithm. Reading: Kozen Chapters 13,14

19. Feb 17: Myhill-Nerode theorem, using MN to prove non-regularity, Algorithms for regular sets (membership, emptiness, equivalence). Reading: Kozen Chapter 15,16.

20. Feb 20: Recap of Finite Automata, 2-DFA: definition, examples. Proof of equivalence with DFAs. Reading: Kozen Chapters 17,18

21. Feb 22: Pusdown Automata: definition, examples.  Reading: Kozen Chapter 23.

22. Feb 23: CFLs, configurations in a PDA, acceptance, Context-free grammars. Reading: Kozen Chapters 23, E, 19

23. Feb 27: CFGs: Examples, Ambiguity, Parse Trees, Chomsky Normal Form. Reading: Kozen Chapters 20, 21

24. Mar 1: Limitations of CFGS: Pumping Lemma for CFLs, examples. Reading: Chapter 22.

25. Mar 2: Equivalence of PDA and CFG. Reading: Chapters 24, 25.

26. Mar 4-12: Semester break.

27. Mar 13: Closure properties of CFLs,  Computational problems: Membership (CKY algorithm), etc. Reading: Kozen Chapters 25, 27.

28. Mar 15: Turing Machines: definition, Turing recognizable, decidable sets, examples. Reading: Sipser Chapter 3.

29. Mar 17: Turing Machines: decidability vs recognizability, variants: k-tape machines. Reading: Sipser Chapter 3.

30. Mar 20: Turing Machine variants: k-tape, enumerators vs recognizers. Reading: Sipser Chapter 3, Kozen Chapter 28, 29.

31. Mar 22: Turing Machine variants: queue machines, 2 stacks, NDTMs, Church-Turing thesis. Reading: Sipser Chapter 3, Kozen Chapter 30.

32. Mar 23-26: Minor week

33. Mar 27:  Undecidability: Acceptance problems for Turing machines, Diagonalisation,  Universal Turing machines. Reading: Sipser Chapter 4

34. Mar 29: Reductions: reducing A_{TM} to halting problem, emptiness problem, language equivalence. Reading: Sipser Chapter 5

35. Apr 3: Reductions: A_{TM} to REG, many-one/mapping reductions. Reading: Sipser Chapter 5.

36. Apr 5: Reductions: Computation history method, Linearly Bounded Automata (membership, emptiness). Reading: Sipser Chapter 5.

37. Apr 6: Reductions: Undecidable problems about CFLs, Undecidability of PCP. Reading: Sipser Chapter 5, Kozen Chapter 35. 

38. Apr 10: Rice's Theorem: Examples, Usage. Reading: Kozen Chapter 34.

39. Apr 12: Rice's Theorem: Proof, how to use Rice's theorem. Reading: Kozen Chapter 34.

40. Apr 13: Beyond undecidability: Oracle Turing machines, Arithmetic Hierarchy, a quantifier-based viewpoint. Reading: Kozen Chapter J.

41. Apr 17: Computational Complexity Theory 1: Time complexity, classes: P, NP, EXP. Space Complexity: PSPACE, NSPACE, LOG, NLOG.

42. Apr 19: Quiz 3

43. Apr 20: Computational Complexity Theory 2: 

44. Apr 24: Computational Complexity Theory 3:

45. Apr 26: 

46. Apr 27:

47.