CS386 - Teaching Material - Spring 2007

Lectures

1. 3/26/07: Course overview. Basic set theory. Powerset and cartesian product. Functions and relations. Countable and uncountable sets.


2. 3/28/07: Proofs techniques. Proofs by contradiction and proofs by induction. Cantor's theorem. Alphabets, strings and languages.


3. 4/2/07: DFAs. Transition function and extended transition function. Transition graphs. Language recognized by a DFA. Simulation of a DFA. Examples: numerical literals and detecting patterns in a string.


4. 4/5/07: NFAs with lambda transitions. Lambda-closure. Extended transition function in NFAs. Language recognized by an NFA. The subset construction.


5. 4/9/07: Correctness of the subset construction. Critical cases in the subset construction. Design of a DFA for a specific language. Exercises.

   Next Lecture: preparation to MT1.



6. 4/11/07: Equivalence relations. Equivalence of states relation. Minimization of DFAs. Uniqueness of the minimized DFA.


7. 4/16/07: Regular expressions: syntax and semantics. Building an NFA given a regular expression. Testing the equivalence between regular expressions.


8. 4/18/07: MT1.


9. 4/23/07: Review of MT1. Grammars. One-step derivation. Language generated by a grammar. Right-linear and Left-linear grammars. Equivalence between NFA and Right-linear grammars.


10. 4/25/07: Deriving regular expressions from NFAs: state elimination.


11. 4/30/07: Properties of regular expressions: closure under homomorphisms, inverse homomorphisms and quotients.


12. 5/2/07: Proving regularity of languages by the application of regularity preserving operations to regular languages. Nonregular languages. Pumping lemma.


13. 5/7/07: Preparation to MT2. Review on subset construction, minimization, regular expressions, right-linear grammars, homomorphism, quotients and Pumping Lemma.


14. 5/9/07: MT2.


15. 5/14/07: Context Free Grammars. Parse Trees. Leftmost and rightmost derivations. Ambiguity.


16. 5/16/07: Chomsky Normal Form. Deciding the parsing problem in cubic time. Grammar transformations: elimination of useless symbols.


17. 5/21/07: Elimination of useless symbols, lambda-productions and unit-productions. Obtaining the Chomsky Normal Form. Introduction to PDAs: instantaneous descriptions, moves and language recognized by a PDA. Graph representation. Examples.


18. 5/23/07: Pushdown Automata and Context Free Grammars.


19. 5/30/07: Preparation to the final exam.

Announcements

• 4/16/2007: MT1 (postponed to 4/18/2007). Topics: chapters 1,2 (except graphs, trees and grammars).
• 5/9/2007: MT2 (posted 4/30/2007). Topics: up to chapter 4 inclusive.

Downloads

• sample mt1
• 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.