- Meeting 01 : Mon, Jan 09, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Administrative announcements. Outline of the course. Introduction, perspectives on computation.
- Meeting 02 : Tue, Jan 10, 10:00 pm-10:50 pm
References | |
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
References | |
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
References | |
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.
- Meeting 05 : Mon, Jan 16, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Examples (contd): Word language of a finite group. Proving correctness of DFA. More examples.
- Meeting 06 : Tue, Jan 17, 10:00 pm-10:50 pm
References | |
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.
- Meeting 07 : Wed, Jan 18, 09:00 am-09:50 am
References | |
Exercises | |
Reading | |
Proof of closure properties. Intersection: product construction. Complementation. Concatenation.
- Meeting 08 : Mon, Jan 23, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Class Cancelled.
- Meeting 09 : Tue, Jan 24, 10:00 pm-10:50 pm
References | |
Exercises | |
Reading | |
Proof of closure properties. Limitations of regular languages.
- Meeting 10 : Wed, Jan 25, 09:00 am-09:50 am
References | |
Exercises | |
Reading | |
Limitiations of regular languages: Pumping Lemma.
Proving that a language is not regular. Games against the demon.
- Meeting 11 : Mon, Jan 30, 11:00 am-11:50 am
References | |
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.
- Meeting 12 : Wed, Feb 01, 09:00 am-09:50 am
References | |
Exercises | |
Reading | |
Quotient Construction (contd). DFA state minimization algorithm. Examples. Proof of correctness.
Structural properties of regular languages.
- Meeting 13 : Mon, Feb 06, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Myhill-Nerode relations.
- Meeting 14 : Tue, Feb 07, 10:00 pm-10:50 pm
References | |
Exercises | |
Reading | |
Myhill-Nerode relations (contd) Myhill-Nerode theorem.
- Meeting 15 : Wed, Feb 08, 09:00 am-09:50 am
References | |
Exercises | |
Reading | |
Myhill-Nerode theorem. DFAs with two way access.
References: | [Koz] A set of Slides on Myhill Nerode Theorem.
|