CS386 - Teaching Material - Fall 2007

Lectures

1. 9/20/07: Course overview. Basic set theory. Powerset and cartesian product. Functions and relations.


2. 9/25/07: Injections, surjections and bijections. Cantor's theorem. Countable and uncountable sets.


3. 9/27/07: Equivalence relations. Propositional connectives, truth tables and tautologies. Proof techniques: by contradiction and by induction. Alphabets, words and languages.

   Study up to cp 1.2.



4. 10/02/07: String operations: concatenation and reversal. Operations between languages: union, concatenation and star closure. Introduction to Finite State Automata. Transition Graphs.


5. 10/04/07: DFAs. Extended transition function. Language accepted by a DFA. Introduction to nondeterministic FAs (NFAs). Criterion of acceptance in an NFA.


6. 10/09/07: NFAs with lambda transitions. Extended transition function. Language accepted by an NFA. The subset construction. A bad case for the subset construction.


7. 10/11/07: Correctness of the Subset construction. Minimization of DFAs: the quotient construction.


8. 10/16/07: Uniqueness of the minimum DFA. Operations on DFA: complement, concatenation and union. Preparation to MT1.


9. 10/18/07: MT1.


10. 10/23/07: Review of MT1. Regular expressions: syntax and semantics. From RegExps to NFAs.


11. 10/25/07: From NFAs to RegExps: the state elimination procedure.


12. 10/30/07: More on DFA minimization. The Table-filling method. The L-equivalence relation. Nerode's theorem.


13. 11/1/07: Grammars. The Chomsky Hierarchy. Right-Linear Grammars. From DFAs to Right-Linear Grammars.


14. 11/6/07: From Right-Linear Grammars to NFAs. Left-linear grammars. Closure properties of regular languages. Language homomorphisms, inverse homomorphisms and quotients.


15. 11/8/07: Proving nonregularity: Pumping Lemma. Use of closure properties.


16. 11/13/07: Preparation to MT2.


17. 11/15/07: MT2.


18. 11/20/07: Review of MT2. Introduction to CFG.


19. 11/27/07: Parse Trees, Leftmost and Rightmost Derivations. Ambiguity.

Announcements

• 10/09/2007: MT1 is on Thursday, 10/18/2007. Topics: chapters 1,2 (except graphs, trees and grammars).


• 10/15/2007: Today, Monday 15, office hours are canceled.


• 11/5/2007: MT2 is on Thursday, 11/15/2007. Topics: up to chapter 4 inclusive.


• 11/25/2007: Tomorrow, Monday 26, office hours will be canceled.

Downloads

• sample mt1 (username/password will be announced in class on Thursday, 11).


• sample mt2.
• sample final

CSNS - Computer Science Network Services

Assignments and exams should be uploaded by the due date through the CSNS - Computer Science Network Services website. If you have never used this system before then follow the instructions for students.