CS386 Teaching Material

CS386 - Teaching Material - Spring 2004

Lecture 1, 3/29/2004.
Basics of Set Theory. Set operations and their properties. The Russell's paradox. Elements of Propositional Logic. Variables, connectives, truth tables.
Reading Assignment: 1.2, 1.3 (from textbook).

Lecture 2, 4/5/2004.
Logical systems: syntax, semantics, inference rules. Propositional Logic: well-formed formulas, satisfiability, Hilbert-type calculus. Notion of formal proof in a logical system. Soundness and completeness of the Hilbert calculus. Statement of Godel's completeness theorem for the propositional logic. Tautologies and contradictions. The contrapositive tautology. Proofs Techniques: direct proofs, proofs by contradiction and by the use of the contrapositive tautology.
Reading Assignment: Chapter 1.

Lecture 3, 4/7/2004.
Review of the previous lecture. Examples of proof techniques. Simple induction and Structural induction.

Lecture 4, 4/12/2004.
Alphabets, Strings and Languages. Operations on languages. Overview on Grammars and Automata.

Lecture 5, 4/14/2004.
Deterministic Finite State Automata (DFSA). Transition Graphs. Extended transition function. Language accepted by a DFSA.

Lecture 6, 4/19/2004.
Nondeterministic Finite State Automata (NFSA). Extended transition function. Language accepted by a NFSA.

Lecture 7, 4/21/2004.
Equivalence between NFSA and DFSA: the Subset construction.

Lecture 8, 4/26/2004.
Proof of the correctness of the Subset construction. NFSA with epsilon-transitions. Generalized Subset construction.

Lecture 9, 5/3/2004.
Regular expressions. Construction of an FSA that accepts a language denoted by a given regular expression.

Lecture 10, 5/5/2004.
Derivation of a regular expression that denotes the language accepted by a given FSA. The state elimination procedure.
Reading Assignment: Chapter 3 (all).

Lecture 11, 5/10/2004.
Regular Expressions in Unix. Exercises using grep.
Reading Assignment: Manual of grep.

Lecture 12, 5/12/2004.
Properties of Regular Expressions. Closure properties of Regular Languages. Pumping Lemma.

Lecture 13, 5/17/2004.
Minimization of DFSA. The indistiguishability relation. Minimality of the minimized automaton.

Lecture 14, 5/19/2004.
Context Free grammmars. Language generated by a CF grammar. Context Free Languages.

Lecture 15, 5/24/2004.
Proofs form about grammars. Parse Trees. Leftmost and rightmost derivations. Preparation to the Midterm examination.

Lecture 16 (end of the course), 6/1/2004.
Ambiguity in CFG's. Review.
Reading Assignment: Chapter 5 (except 5.3).

Midterm 1: Wednesday, April 28, 2004. Material to cover: chapters 1 and 2 of the book plus elements of propositional logic (what has been done in class: see logs of the first lectures). Sample of Midterm 1.

Midterm 2: Wednesday, May 26, 2004. Comprehensive with emphasis on last part of the course (up to Chapter 4 inclusive).
Tuesday, May 25: Today no extra lecture. Tomorrow office hours will be held regularly.

Final Exam: Monday, June 7, 2004. Time: 7:30pm-10:30pm.
Note: The exam will be comprehensive (except propositional logic covered in the first lecture). It will be structured as Midterm 2 and will include one exercise on CFG's (Chapter 5).