- 3/28/05: Presentation of the course. Elements of Set
Theory.
Textbook: 1.1
- 3/30/05: Proof techniques. The principle of induction.
Textbook: 1.2-1.5
- 4/4/05: Alphabets, Strings and Languages. Formal definition
of a Deterministic Finite State Automaton. Transition diagrams.
Textbook: 2.1, 2.2.1, 2.2.2, 2.2.3.
- 4/6/05: Extended transition function in a
DFA. Nondeterministic FA (NFA). Extended transition function in an
NFA.
Textbook: 2.2.4-2.3.3.
- 4/11/05: Equivalence between DFA and NFA: the subset construction.
A bad case for the subset construction.
Textbook: 2.3.4-2.3.7.
- 4/13/05: Proof of the correctness of the subset
construction. NFA with epsilon-transitions (EFA). Epsilon
closure. Equivalence between DFA and EFA: the generalized subset
construction.
Textbook: 2.5. (all).
- 4/18/05: Regular expressions: syntax and
semantics. Algebraic laws for regular expressions. Deriving an EFA
that accepts the language denoted by a given regular expression.
Textbook: 3.1, 3.2.3, 3.4.1-3.4.5.
4/20/05: Midterm 1.
- 4/25/05: Review of the midterm examination. Deriving a
regular expression that denotes a language accepted by a given FA.
Textbook: 3.2.1
- 4/27/05: The state elimination procedure. Algebraic laws
for regular expressions. Regular expressions in Unix.
Textbook: 3.2 (all), 3.3.1, 3.4 (all).
- 5/2/05: Pumping Lemma.
Textbook: 4.1.
- 5/4/05: Testing membership in a regular
language. Minimization of DFA.
Textbook: 4.3.3, 4.4.
- 5/9/05: Optimality of the minimization procedure. Closure
properties of regular languages. Matching regular expressions.
Textbook: 4.2.1-4.2.3, 4.4 (all).
- 5/11/05: Matching regular expressions.
Textbook: see cp 9.6 in the cs312-s-05 textbook.
- 5/16/05: Parsing regular expressions. Syntactic charts. A
top-down parser for regular expressions.
Textbook: (not in the book). Read: 5.1.1, 5.1.2
Download programming assignment.
- 5/18/05: Overview on grammars and automata. Context Free
grammars. Derivations. Language generated by a grammar. Proving that a
grammar generates a given language. Sentential forms.
Textbook: 5.1
- 5/23/05: Midterm 2.
- 5/25/05: Leftmost and Rightmost derivations. Parse
Trees. Ambiguity.
- 6/1/05: General overview. Examples of ambiguous
grammars.