CS2200 - Languages, Machines and Computation

Meetings  

• Theme 1 : Finite Automata and Regular Languages  - 15 meetings

  • Meeting 01 : Mon, Jan 09, 11:00 am-11: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.

  • Meeting 02 : Tue, Jan 10, 10:00 pm-10:50 pm

  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!!

  • Meeting 03 : Wed, Jan 11, 09:00 am-09:50 am

  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].

  • Meeting 04 : Thu, Jan 12, 01:00 pm-01:50 pm

  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]

  • Meeting 05 : Mon, Jan 16, 11:00 am-11:50 am

  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]

  • Meeting 06 : Tue, Jan 17, 10:00 pm-10:50 pm

  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]

  • Meeting 07 : Wed, Jan 18, 09:00 am-09:50 am

  Proof of closure properties. Intersection: product construction. Complementation. Concatenation.

  References	[Koz]
  Exercises
  Reading

  Proof of closure properties. Intersection: product construction. Complementation. Concatenation.
  

  References:

  [Koz]

  • Meeting 08 : Mon, Jan 23, 11:00 am-11:50 am

  Class Cancelled.

  References
  Exercises
  Reading

  Class Cancelled.
  

  References:

  None

  • Meeting 09 : Tue, Jan 24, 10:00 pm-10:50 pm

  Proof of closure properties. Limitations of regular languages.

  References	[Koz]
  Exercises
  Reading

  Proof of closure properties. Limitations of regular languages.
  

  References:

  [Koz]

  • Meeting 10 : Wed, Jan 25, 09:00 am-09:50 am

  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]

  • Meeting 11 : Mon, Jan 30, 11:00 am-11:50 am

  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]

  • Meeting 12 : Wed, Feb 01, 09:00 am-09:50 am

  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]

  • Meeting 13 : Mon, Feb 06, 11:00 am-11:50 am

  Myhill-Nerode relations.

  References	[Koz]
  Exercises
  Reading

  Myhill-Nerode relations.
  

  References:

  [Koz]

  • Meeting 14 : Tue, Feb 07, 10:00 pm-10:50 pm

  Myhill-Nerode relations (contd) Myhill-Nerode theorem.

  References	[Koz]
  Exercises
  Reading

  Myhill-Nerode relations (contd) Myhill-Nerode theorem.
  

  References:

  [Koz]

  • Meeting 15 : Wed, Feb 08, 09:00 am-09:50 am

  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

  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

  • Meeting 17 : Tue, Feb 14, 10:00 pm-10:50 pm

  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

  • Meeting 18 : Wed, Feb 15, 09:00 am-09:50 am

  Formal definition of NFAs. Definition of acceptance.

  References
  Exercises
  Reading

  Formal definition of NFAs. Definition of acceptance.
  

  References:

  None

  • Meeting 19 : Mon, Feb 20, 11:00 am-11:50 am

  Examples of NFAs. Subset construction.

  References
  Exercises
  Reading

  Examples of NFAs. Subset construction.
  

  References:

  None

  • Meeting 20 : Wed, Feb 22, 09:00 am-09:50 am

  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

  • Meeting 21 : Thu, Feb 23, 01:00 pm-01:50 pm

  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

  • Meeting 22 : Mon, Feb 27, 11:00 am-11:50 am

  Converting NFAs to regex and vice versa.

  References
  Exercises
  Reading

  Converting NFAs to regex and vice versa.
  

  References:

  None

  • Meeting 23 : Tue, Feb 28, 10:00 pm-10:50 pm

  Homomorphisms. Closure of regular languages under homomorphisms. Examples.

  References
  Exercises
  Reading

  Homomorphisms. Closure of regular languages under homomorphisms. Examples.
  

  References:

  None

  • Meeting 24 : Wed, Mar 01, 09:00 am-09:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 25 : Thu, Mar 02, 01:00 pm-01:50 pm

  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

  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

  • Meeting 27 : Tue, Mar 07, 10:00 pm-10:50 pm

  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

  • Meeting 28 : Wed, Mar 08, 09:00 am-09:50 am

  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

  • Meeting 29 : Mon, Mar 13, 11:00 am-11:50 am

  Non instructional day

  References
  Exercises
  Reading

  Non instructional day
  

  References:

  None

  • Meeting 30 : Tue, Mar 14, 10:00 pm-10:50 pm

  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

  • Meeting 31 : Wed, Mar 15, 09:00 am-09:50 am

  Using pumping lemma for CFGs. Push Down Automata

  References
  Exercises
  Reading

  Using pumping lemma for CFGs. Push Down Automata
  

  References:

  None

  • Meeting 32 : Mon, Mar 20, 11:00 am-11:50 am

  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

  • Meeting 33 : Tue, Mar 21, 10:00 pm-10:50 pm

  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

  • Meeting 34 : Wed, Mar 22, 09:00 am-09:50 am

  Pushdown automata and context free grammars. CFG to PDA

  References
  Exercises
  Reading

  Pushdown automata and context free grammars. CFG to PDA
  

  References:

  None

  • Meeting 35 : Mon, Mar 27, 11:00 am-11:50 am

  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

  • Meeting 36 : Tue, Mar 28, 10:00 pm-10:50 pm

  Holiday - Ugadi

  References
  Exercises
  Reading

  Holiday - Ugadi
  

  References:

  None

  • Meeting 37 : Thu, Mar 30, 01:00 pm-01:50 pm

  PDAs to single state PDAs: Detailed construction with proof.

  References
  Exercises
  Reading

  PDAs to single state PDAs: Detailed construction with proof.
  

  References:

  None

  • Meeting 38 : Mon, Apr 03, 11:00 am-11:50 am

  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

  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

  • Meeting 40 : Wed, Apr 05, 09:00 am-09:50 am

  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

  • Meeting 41 : Mon, Apr 10, 11:00 am-11:50 am

  Notion of acceptance. Another example: high level description only.

  References
  Exercises
  Reading

  Notion of acceptance. Another example: high level description only.
  

  References:

  None

  • Meeting 42 : Tue, Apr 11, 10:00 pm-10:50 pm

  Multi tape Turing machines. Other generalisations.

  References
  Exercises
  Reading

  Multi tape Turing machines. Other generalisations.
  

  References:

  None

  • Meeting 43 : Wed, Apr 12, 09:00 am-09:50 am

  No lecture (time table change)

  References
  Exercises
  Reading

  No lecture (time table change)
  

  References:

  None

  • Meeting 44 : Thu, Apr 13, 01:00 pm-01:50 pm

  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

  • Meeting 45 : Mon, Apr 17, 11:00 am-11:50 am

  Halting problem is not recursive. using Cantor's diagonalization.

  References
  Exercises
  Reading

  Halting problem is not recursive. using Cantor's diagonalization.
  

  References:

  None

  • Meeting 46 : Tue, Apr 18, 10:00 pm-10:50 pm

  More non-recursive languages. Reductions.

  References
  Exercises
  Reading

  More non-recursive languages. Reductions.
  

  References:

  None

  • Meeting 47 : Wed, Apr 19, 09:00 am-09:50 am

  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

  Tutorial - 1. Topics to be covered: Lectures 1-6.

  References
  Exercises
  Reading

  Tutorial - 1. Topics to be covered: Lectures 1-6.
  

  References:

  None

  • Meeting 49 : Tue, Jan 31, 10:00 pm-10:50 pm

  Tutorial - 2.

  References
  Exercises
  Reading

  Tutorial - 2.
  

  References:

  None

  • Meeting 50 : Thu, Feb 02, 01:00 pm-01:50 pm

  Short Exam - 1

  References
  Exercises
  Reading

  Short Exam - 1
  

  References:

  None

  • Meeting 51 : Thu, Feb 09, 01:00 pm-01:50 pm

  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

  • Meeting 52 : Thu, Feb 16, 01:00 pm-01:50 pm

  Tutorial - 3

  References
  Exercises
  Reading

  Tutorial - 3
  

  References:

  None

  • Meeting 53 : Thu, Mar 09, 01:00 pm-01:50 pm

  Tutorial 4

  References
  Exercises
  Reading

  Tutorial 4
  

  References:

  None

  • Meeting 54 : Thu, Mar 16, 01:00 pm-01:50 pm

  Tutorial 5

  References
  Exercises
  Reading

  Tutorial 5
  

  References:

  None

  • Meeting 55 : Thu, Mar 23, 01:00 pm-01:50 pm

  Tutorial 6

  References
  Exercises
  Reading

  Tutorial 6
  

  References:

  None

  • Meeting 56 : Thu, Apr 06, 01:00 pm-01:50 pm

  Tutorial - 7

  References
  Exercises
  Reading

  Tutorial - 7
  

  References:

  None

• Theme 6 : Exams - 4 meetings

  • Meeting 57 : Tue, Feb 21, 10:00 pm-10:50 pm

  Quiz - 1 Lectures 1 - 18.

  References
  Exercises
  Reading

  Quiz - 1 Lectures 1 - 18.
  

  References:

  None

  • Meeting 58 : Wed, Mar 29, 09:00 am-09:50 am

  Quiz 2. Syllabus: Lectures 18-34

  References
  Exercises
  Reading

  Quiz 2. Syllabus: Lectures 18-34
  

  References:

  None

  • Meeting 59 : Thu, Apr 20, 12:00 pm-01:15 pm

  Short Exam - 2 Syllabus: Lecture 12- 45.

  References
  Exercises
  Reading

  Short Exam - 2 Syllabus: Lecture 12- 45.
  

  References:

  None

  • Meeting 60 : Thu, Apr 27, 09:00 am-12:00 pm

  Syllabus: Everything covered in the class and Tutorials.

  References
  Exercises
  Reading

  Syllabus: Everything covered in the class and Tutorials.
  

  References:

  None