CS386 - Teaching Material - Fall 2006

Lectures

1. 9/21/06: Presentation of the course. Mathematical preliminaries: set theory (1.1).


2. 9/26/06: Functions and Relations. Injections, surjections and bijections. Equivalence Relations. Countable sets. Noncountable sets: Cantor's theorem. Proofs by contradiction (1.1).


3. 9/28/06: Proof techniques: the principle of induction. Graphs and Trees. Alphabets, words and languages.


4. 10/3/06: Language operations. Deterministic Finite State Automata (DFA). Transition graphs. Extension of the transition function. Language accepted by a DFA.


5. 10/5/06: Nondeterministic Finite State Automata (NFA). Extension of the transition function. Language accepted by an NFA. Equivalence between NFA and DFA: the subset construction.

   Section 2.2, 2.3.



6. 10/10/06: Exercises on NFAs and DFAs.


7. 10/12/06: Critical cases for the Subset construction. Building DFAs that accept the intersection or the union of regular languages.


8. 10/17/06: MT1.


9. 10/19/06: Review of MT1. Minimization of DFAs.


10. 10/24/06: Optimality of the minimization procedure. Regular expressions: syntax and semantics. From regular expressions to NFAs. From NFAs to regular expressions: state elimination.


11. 10/26/06: Application of regular expressions: grep. Grammars. One-step derivation. Language generated by a grammar. Right-linear grammars. Equivalence between right-linear grammars and DFAs.


12. 10/31/06: Pumping Lemma.


13. 11/2/06: A CF grammar for the palindromes of even length. Closure Properties of regular languages: reversal, homomorphism and inverse homomorphism.


14. 11/7/06: Closure with respect to left and right quotients.


15. 11/9/06: Exercises.


16. 11/14/06: MT2.


17. 11/16/06: Review of MT2. Context Free grammars.


18. 11/21/06: Leftmost and rightmost derivations. Derivation Trees. Ambiguity.


19. 11/28/06: Chomsky Normal Form (CNF). Deciding the membership problem for CFGs in cubic time. Methods for transforming grammars: elimination of useless productions and lambda-productions (cp 6).


20. 11/30/06: Elimination of unit-productions. Construction of the CNF. Exercises.

Announcements

• 10/12/2006: MT1. Topics: 1.1, 1.2 (except Grammars), 2.1, 2.2, 2.3. Postponed to Tuesday 10/17/2006.


• 11/14/2006: MT2. Topics: up to chapter 4 (inclusive). Sample Midterm


• Wednesday, November 15, OH will be held from 10am to 12am.


• 12/7/2006: Final. Topics: up to chapter 6 (inclusive). 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.