CS386 - Teaching Material - Fall 2005

Lectures

1. 9/22/05: Introduction to Propositional Logic: well-formed formulas, Semantics, Hilbert calculus. Syntactic and Semantic consequences. Soundness and completeness of the Hilbert Calculus. Tautologies. Proof techniques: deductive proves, proves by the contrapositive and by contradiction.



2. 9/27/05: Elements of elementary set theory. Set operations. Identities involving set operations. Cardinality of a set. Proving equivalences about sets. Countability of the rational numbers.

   Textbook: 1.1-1.3.




3. 9/29/05: Inductive proofs. Alphabets, strings and languages.

   Textbook: 1.4-1.5.




4. 10/4/05: Deterministic finite state automata (DFA). Extended Transition function. Examples.

   Textbook: 2.1-2.2.




5. 10/6/05: Nondeterministic finite state automata (NFA). Extended transition function. Examples.

   Textbook: 2.3-2.4.




6. 10/11/05: Equivalence between NFA and DFA: the Subset Construction.

   Textbook: 2.3.5-2.3.6. (2.3 all)




7. 10/13/05: NFA with epsilon transitions. Epsilon closures. The generalized Subset Construction.

   Textbook: cp 2 (all).




8. 10/18/05: Midterm 1.



9. 10/20/05: Review of the Midterm examination. Regular expressions: syntax and semantics. Building NFA with epsilon transitions that accept the language denoted by a given regular expression.

   Textbook: cp 3.1, 3.2.3.




10. 10/25/05: Deriving regular expressions from NFA. State Elimination. Algebraic laws for regular expressions.

    Textbook: cp 3.2, 3.4.




11. 10/27/05: In-class exam.
    
    
12. 11/1/05: Pumping Lemma.

    Textbook: cp 4.1.




13. 11/3/05: Minimization of DFA. The problem of the equivalence of regular languages. Uniqueness of the minimum automaton. Regular expressions in Unix.

    Textbook: cp 3.3,4.3,4.4.




14. 11/8/05: Closure properties of Regular Languages: reversal, homomorphism and inverse homomorphism.

    Textbook: cp 4.2




15. 11/10/05: Grammars. Linear and Context Free Grammars. One-step derivation and Many-step derivation. Sentential forms. Language generated by a grammar. Leftmost and rightmost derivations. Parse Trees. Ambiguity.

    Textbook: cp 5




16. 11/15/05: MT2.



17. 11/17/05: Applications of Automata Theory to parsing: Lex and Yacc specifications.



18. 11/22/05: Pushdown Automata (PDA). Acceptance by empty stack and by final state. Equivalence between PDA's and CFG's.



19. 11/29/05: Construction of a CFG equivalent to a given PDA. Deterministic PDA (DPDA). Deterministic languages and ambiguity.



20. 12/01/05: Course recap. Exercises. Equivalence of regular expressions.

Assignments

1. 10/27/2005: in-class test

Important Deadlines

1. Tuesday 10/18/2005: Midterm 1. Topics: chapters 1 and 2.


2. Thursday 10/27/2005: In-class Test. Preparation to the Second Midterm. Topics: chapter 1, 2 and 3.


3. Tuesday 11/15/2005: Midterm 2. Topics: chapters 3 and 4. Subset construction, DFA minimization, design of FA given the language, deriving regular expressions given the FA, Pumping Lemma, closure properties of Regular Languages. No grammars.