Meetings

Click on the theme item for the meeting plan for that theme.Click on the meeting item for references, exercises, and additional reading related to it.

**Theme 1 : Finite Automata and Regular Languages**- 15 meetings- Meeting 01 : Mon, Jan 09, 11:00 am-11:50 am
- Meeting 02 : Tue, Jan 10, 10:00 pm-10:50 pm
- Meeting 03 : Wed, Jan 11, 09:00 am-09:50 am
- Meeting 04 : Thu, Jan 12, 01:00 pm-01:50 pm
- Meeting 05 : Mon, Jan 16, 11:00 am-11:50 am
- Meeting 06 : Tue, Jan 17, 10:00 pm-10:50 pm
- Meeting 07 : Wed, Jan 18, 09:00 am-09:50 am
- Meeting 08 : Mon, Jan 23, 11:00 am-11:50 am
- Meeting 09 : Tue, Jan 24, 10:00 pm-10:50 pm
- Meeting 10 : Wed, Jan 25, 09:00 am-09:50 am
- Meeting 11 : Mon, Jan 30, 11:00 am-11:50 am
- Meeting 12 : Wed, Feb 01, 09:00 am-09:50 am
- Meeting 13 : Mon, Feb 06, 11:00 am-11:50 am
- Meeting 14 : Tue, Feb 07, 10:00 pm-10:50 pm
- Meeting 15 : Wed, Feb 08, 09:00 am-09:50 am

Administrative announcements. Outline of the course. Introduction, perspectives on computation. References None. Exercises Reading Administrative announcements. Outline of the course. Introduction, perspectives on computation.References: None. Elementary notions of computation. Example notions of computation: Model for arithmetic computation. References Your own class notes!! Exercises Reading Elementary notions of computation. Example notions of computation: Model for arithmetic computation.References: Your own class notes!! Finite state systems. Formal definition of a finite automata. References First chapter in [Koz]. Exercises Reading Finite state systems. Formal definition of a finite automata.References: First chapter in [Koz]. Notion of acceptance in a DFA. Examples: 1) Strings with even number of a's, 2) Number of a'1 is 1 modulo 5. References [Koz] Exercises Reading Notion of acceptance in a DFA. Examples: 1) Strings with even number of a's, 2) Number of a'1 is 1 modulo 5.References: [Koz] Examples (contd): Word language of a finite group. Proving correctness of DFA. More examples. References [Koz] Exercises Reading Examples (contd): Word language of a finite group. Proving correctness of DFA. More examples.References: [Koz] More examples of regular languages. Properties of regular languages. Closure properties: 1) Set theoretic: Union, Intersection, Complementation. 2) String operations: Concatenation, Kleene closure. References [Koz] Exercises Reading More examples of regular languages. Properties of regular languages. Closure properties: 1) Set theoretic: Union, Intersection, Complementation. 2) String operations: Concatenation, Kleene closure.References: [Koz] Proof of closure properties. Intersection: product construction. Complementation. Concatenation. References [Koz] Exercises Reading Proof of closure properties. Intersection: product construction. Complementation. Concatenation.References: [Koz] Class Cancelled. References Exercises Reading Class Cancelled.References: None Proof of closure properties. Limitations of regular languages. References [Koz] Exercises Reading Proof of closure properties. Limitations of regular languages.References: [Koz] Limitiations of regular languages: Pumping Lemma. Proving that a language is not regular. Games against the demon. References [Koz] Exercises Reading Limitiations of regular languages: Pumping Lemma. Proving that a language is not regular. Games against the demon.References: [Koz] More examples of non-regular languages. What is the minimum number of states required for a DFA to accept a given regular language? DFA state minimization. Quotient construction. References [Koz] Exercises Reading More examples of non-regular languages. What is the minimum number of states required for a DFA to accept a given regular language? DFA state minimization. Quotient construction.References: [Koz] Quotient Construction (contd). DFA state minimization algorithm. Examples. Proof of correctness. Structural properties of regular languages. References [Koz] Exercises Reading Quotient Construction (contd). DFA state minimization algorithm. Examples. Proof of correctness. Structural properties of regular languages.References: [Koz] Myhill-Nerode relations. References [Koz] Exercises Reading Myhill-Nerode relations.References: [Koz] Myhill-Nerode relations (contd) Myhill-Nerode theorem. References [Koz] Exercises Reading Myhill-Nerode relations (contd) Myhill-Nerode theorem.References: [Koz] Myhill-Nerode theorem. DFAs with two way access. References [Koz] A set of <a href="https://drona.csa.iisc.ernet.in/~deepakd/atc-2010/myhill-nerode-priti.pdf"> Slides </a> on Myhill Nerode Theorem. Exercises Reading Myhill-Nerode theorem. DFAs with two way access.References: [Koz] A set of Slides on Myhill Nerode Theorem. **Theme 2 : Non-determinism and two-way access**- 10 meetings- Meeting 16 : Mon, Feb 13, 11:00 am-11:50 am
- Meeting 17 : Tue, Feb 14, 10:00 pm-10:50 pm
- Meeting 18 : Wed, Feb 15, 09:00 am-09:50 am
- Meeting 19 : Mon, Feb 20, 11:00 am-11:50 am
- Meeting 20 : Wed, Feb 22, 09:00 am-09:50 am
- Meeting 21 : Thu, Feb 23, 01:00 pm-01:50 pm
- Meeting 22 : Mon, Feb 27, 11:00 am-11:50 am
- Meeting 23 : Tue, Feb 28, 10:00 pm-10:50 pm
- Meeting 24 : Wed, Mar 01, 09:00 am-09:50 am
- Meeting 25 : Thu, Mar 02, 01:00 pm-01:50 pm

Two way DFAs(2DFA). Definition and examples. Notion of configurations. References Exercises Reading Two way DFAs(2DFA). Definition and examples. Notion of configurations.References: None Languages accepted by 2DFAs = Regular Languages. Notion of non-determinism. References Exercises Reading Languages accepted by 2DFAs = Regular Languages. Notion of non-determinism.References: None Formal definition of NFAs. Definition of acceptance. References Exercises Reading Formal definition of NFAs. Definition of acceptance.References: None Examples of NFAs. Subset construction. References Exercises Reading Examples of NFAs. Subset construction.References: None Closure properties of regular languages: concatenation and Kleene closure. Epsilon transitions. Patterns in unix shell and grep. References Exercises Reading Closure properties of regular languages: concatenation and Kleene closure. Epsilon transitions. Patterns in unix shell and grep.References: None Formal definition of patterns. Regular expressions. Regular expressions and patterns represent regular languages. References Exercises Reading Formal definition of patterns. Regular expressions. Regular expressions and patterns represent regular languages.References: None Converting NFAs to regex and vice versa. References Exercises Reading Converting NFAs to regex and vice versa.References: None Homomorphisms. Closure of regular languages under homomorphisms. Examples. References Exercises Reading Homomorphisms. Closure of regular languages under homomorphisms. Examples.References: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None Lecture Cancelled. References Exercises Reading Lecture Cancelled.References: None **Theme 3 : Grammars and context-free languages**- 13 meetings- Meeting 26 : Mon, Mar 06, 11:00 am-11:50 am
- Meeting 27 : Tue, Mar 07, 10:00 pm-10:50 pm
- Meeting 28 : Wed, Mar 08, 09:00 am-09:50 am
- Meeting 29 : Mon, Mar 13, 11:00 am-11:50 am
- Meeting 30 : Tue, Mar 14, 10:00 pm-10:50 pm
- Meeting 31 : Wed, Mar 15, 09:00 am-09:50 am
- Meeting 32 : Mon, Mar 20, 11:00 am-11:50 am
- Meeting 33 : Tue, Mar 21, 10:00 pm-10:50 pm
- Meeting 34 : Wed, Mar 22, 09:00 am-09:50 am
- Meeting 35 : Mon, Mar 27, 11:00 am-11:50 am
- Meeting 36 : Tue, Mar 28, 10:00 pm-10:50 pm
- Meeting 37 : Thu, Mar 30, 01:00 pm-01:50 pm
- Meeting 38 : Mon, Apr 03, 11:00 am-11:50 am

Context free grammars. Productions. Examples. Balanced Paranthesis. Proof of correctness. References Exercises Reading Context free grammars. Productions. Examples. Balanced Paranthesis. Proof of correctness.References: None Balanced Paranthesis: proof of correctness contd. Normal forms for CFGs. References Exercises Reading Balanced Paranthesis: proof of correctness contd. Normal forms for CFGs.References: None Normal forms for CFGs: Chomsky normal form (With proof) and Greibach norm form (without proof). References Exercises Reading Normal forms for CFGs: Chomsky normal form (With proof) and Greibach norm form (without proof).References: None Non instructional day References Exercises Reading Non instructional dayReferences: None Conversion to Chomsky normal form. Removing epsilon and unit productions. A Pumping lemma for CFGs. References Exercises Reading Conversion to Chomsky normal form. Removing epsilon and unit productions. A Pumping lemma for CFGs.References: None Using pumping lemma for CFGs. Push Down Automata References Exercises Reading Using pumping lemma for CFGs. Push Down AutomataReferences: None Non deterministic Pushdown Automaton. Stack based algorithms for the language {a^n b^n}. Developing the notion of Pushdown Automata from the stack based algorithm. References Exercises Reading Non deterministic Pushdown Automaton. Stack based algorithms for the language {a^n b^n}. Developing the notion of Pushdown Automata from the stack based algorithm.References: None Formal Definition of Non Deterministic Pushdown Automaton. Notion of Acceptance: by final state and by empty stack (without proof). Examples. References Exercises Reading Formal Definition of Non Deterministic Pushdown Automaton. Notion of Acceptance: by final state and by empty stack (without proof). Examples.References: None Pushdown automata and context free grammars. CFG to PDA References Exercises Reading Pushdown automata and context free grammars. CFG to PDAReferences: None Constructing PDA: an example for the language consisting of strings with equal number of a's and b's. From PDAs to single state PDAs: Intuition. References Exercises Reading Constructing PDA: an example for the language consisting of strings with equal number of a's and b's. From PDAs to single state PDAs: Intuition.References: None Holiday - Ugadi References Exercises Reading Holiday - UgadiReferences: None PDAs to single state PDAs: Detailed construction with proof. References Exercises Reading PDAs to single state PDAs: Detailed construction with proof.References: None Membership testing for Context free languages. Cocke-Kasami-Younger algorithm. References Exercises Reading Membership testing for Context free languages. Cocke-Kasami-Younger algorithm.References: None **Theme 4 : Turing machines and Computability**- 9 meetings- Meeting 39 : Tue, Apr 04, 10:00 pm-10:50 pm
- Meeting 40 : Wed, Apr 05, 09:00 am-09:50 am
- Meeting 41 : Mon, Apr 10, 11:00 am-11:50 am
- Meeting 42 : Tue, Apr 11, 10:00 pm-10:50 pm
- Meeting 43 : Wed, Apr 12, 09:00 am-09:50 am
- Meeting 44 : Thu, Apr 13, 01:00 pm-01:50 pm
- Meeting 45 : Mon, Apr 17, 11:00 am-11:50 am
- Meeting 46 : Tue, Apr 18, 10:00 pm-10:50 pm
- Meeting 47 : Wed, Apr 19, 09:00 am-09:50 am

Notions of effective computability. Historical perspective. Church-Turing Thesis. Informal definition of Turing machines. References Exercises Reading Notions of effective computability. Historical perspective. Church-Turing Thesis. Informal definition of Turing machines.References: None Formal definition of a Turing Machine. Example: High level description. Full description. Notion of acceptance. References Exercises Reading Formal definition of a Turing Machine. Example: High level description. Full description. Notion of acceptance.References: None Notion of acceptance. Another example: high level description only. References Exercises Reading Notion of acceptance. Another example: high level description only.References: None Multi tape Turing machines. Other generalisations. References Exercises Reading Multi tape Turing machines. Other generalisations.References: None No lecture (time table change) References Exercises Reading No lecture (time table change)References: None Universal Turing machines. Encoding of a TM. Simulation of a TM given by its encoding. Halting and Membership problems. References Exercises Reading Universal Turing machines. Encoding of a TM. Simulation of a TM given by its encoding. Halting and Membership problems.References: None Halting problem is not recursive. using Cantor's diagonalization. References Exercises Reading Halting problem is not recursive. using Cantor's diagonalization.References: None More non-recursive languages. Reductions. References Exercises Reading More non-recursive languages. Reductions.References: None Reductions contd. Concluding remarks. References Exercises Reading Reductions contd. Concluding remarks.References: None **Theme 5 : Tutorial Sessions**- 9 meetings- Meeting 48 : Thu, Jan 19, 01:00 pm-01:50 pm
- Meeting 49 : Tue, Jan 31, 10:00 pm-10:50 pm
- Meeting 50 : Thu, Feb 02, 01:00 pm-01:50 pm
- Meeting 51 : Thu, Feb 09, 01:00 pm-01:50 pm
- Meeting 52 : Thu, Feb 16, 01:00 pm-01:50 pm
- Meeting 53 : Thu, Mar 09, 01:00 pm-01:50 pm
- Meeting 54 : Thu, Mar 16, 01:00 pm-01:50 pm
- Meeting 55 : Thu, Mar 23, 01:00 pm-01:50 pm
- Meeting 56 : Thu, Apr 06, 01:00 pm-01:50 pm

Tutorial - 1. Topics to be covered: Lectures 1-6. References Exercises Reading Tutorial - 1. Topics to be covered: Lectures 1-6.References: None Tutorial - 2. References Exercises Reading Tutorial - 2.References: None Short Exam - 1 References Exercises Reading Short Exam - 1References: None Continued from Tutorial 2. Discussion of solutions to SE - 1. References Exercises Reading Continued from Tutorial 2. Discussion of solutions to SE - 1.References: None Tutorial - 3 References Exercises Reading Tutorial - 3References: None Tutorial 4 References Exercises Reading Tutorial 4References: None Tutorial 5 References Exercises Reading Tutorial 5References: None Tutorial 6 References Exercises Reading Tutorial 6References: None Tutorial - 7 References Exercises Reading Tutorial - 7References: None **Theme 6 : Exams**- 4 meetings- Meeting 57 : Tue, Feb 21, 10:00 pm-10:50 pm
- Meeting 58 : Wed, Mar 29, 09:00 am-09:50 am
- Meeting 59 : Thu, Apr 20, 12:00 pm-01:15 pm
- Meeting 60 : Thu, Apr 27, 09:00 am-12:00 pm

Quiz - 1 Lectures 1 - 18. References Exercises Reading Quiz - 1 Lectures 1 - 18.References: None Quiz 2. Syllabus: Lectures 18-34 References Exercises Reading Quiz 2. Syllabus: Lectures 18-34References: None Short Exam - 2 Syllabus: Lecture 12- 45. References Exercises Reading Short Exam - 2 Syllabus: Lecture 12- 45.References: None Syllabus: Everything covered in the class and Tutorials. References Exercises Reading Syllabus: Everything covered in the class and Tutorials.References: None