back to cs386-syllabus

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.