CS 3500 B Theory I - Part 2

Topics

Date(s)

Reading

Definition of deterministic finite automata
Regular languages.
Nondeterministic finite automata.

Tue., Mar. 2

Reading: Sipser Chapters 0 and 1 and 1st set of Lecture Notes.

Closure under regular operations.
Equivalence between NFA and DFA.

Thu., Mar. 4

Reading: Sipser Chapter 1 and 1st set of Lecture Notes.

Regular expressions.
Generalized NFA.
Equivalence between Regular Languages and Regular Expressions.

Tue., Mar. 16

Reading: Sipser Chapter 1 and 2nd set of Lecture Notes.

Proving languages are not regular.
Diagonalization and Cardinality Arguments.
The Pumping Lemma.
Reductions.

Thu., Mar. 18

Reading: Sipser Chapter 1 and 2nd set of Lecture Notes.

Context Free Grammars.
Ambiguity.
All Regular Languages are Context Free.
Closure under union, *, concatenation, but not intersection.

Tue., Mar. 23

Reading: Sipser Chapter 2 and 3rd set of Lecture Notes.

Context Free Grammars.
Chomsky Normal Form.
Pushdown Automata.

Thu., Mar. 25

Reading: Sipser Chapter 2 and 4th set of Lecture Notes.

Context Free Grammars.
Equivalence of CFG and PDA.

Tue., Mar. 30

Reading: Sipser Chapter 2 and 4th set of Lecture Notes.

Quiz 3

Thu., Apr. 1

Material from last quiz until Mar. 25.

Context Free Grammars.
Pumping Lemma for CFL.

Tue., Apr. 6

Reading: Sipser Chapter 2 and 5th set of Lecture Notes.

Turing Machines.
Decidable Problems.

Thu., Apr. 8

Reading: Sipser Chapters 3, 4 and 6th set of Lecture Notes.

Decidable Problems.
Undecidable Problems.
Reductions.

Tue., Apr. 13

Reading: Sipser Chapters 4, 5 and 7th set of Lecture Notes.

Quiz 3.

Thu., Apr. 15

Pumping lemma for regular languages, context free languages, Turing Machines, Decidability, parts of Reducibility (that is, all the material we cover up to April 13th.)

Computational Complexity.
The classes P and NP.
NP-Completeness.
NP-Complete Problems.

Apr. 20 - April 22

Reading: Sipser Chapter 7 and 8th set of Lecture Notes. and, optionally, CLRS Chapter 34.