CS341
Automata Theory
Elaine Rich
Schedule of Classes
|
Week |
Topics |
|
|
Aug. 27 |
Why study automata theory? |
|
|
What is a language? |
|
|
|
Sept. 1 |
The big picture |
|
|
Finite state machines |
|
|
|
Nondeterministic finite
state machines |
|
|
|
Sept. 8 |
Finite state transducers |
|
|
Regular expressions |
|
|
|
Equivalence of regular
expressions and FSMs |
|
|
|
Sept. 15 |
Closure properties of
regular languages |
|
|
Regular Pumping Theorem |
|
|
|
Pumping Theorem and
closure |
|
|
|
Sept. 22 |
Functions on regular
languages |
|
|
Decision procedures for
regular languages |
|
|
|
Review of regular
languages |
|
|
|
Sept. 29 |
Context-free grammars |
Tuesday evening: Midterm 1
|
|
Manipulating context-free
grammars |
|
|
|
Parse trees |
|
|
|
Ambiguity |
|
|
|
Oct. 6 |
Pushdown automata |
|
|
Equivalence of PDAs and CFGs |
|
|
|
Oct. 13 |
Context-Free Pumping
Theorem |
|
|
Closure properties of context-free
languages |
|
|
|
Oct. 20 |
Decision procedures for
context-free languages |
|
|
Turing machines |
|
|
|
Multiple tapes and nondeterminism |
|
|
|
Oct. 27 |
Simulating real computers |
Tuesday evening: Midterm 2 |
|
The Universal Turing
machine |
|
|
|
Church’s Thesis |
|
|
|
Other computational models |
|
|
|
Nov. 3 |
The unsolvability
of the halting problem |
|
|
Decidable and semidecidable languages |
|
|
|
Reduction proofs for undecidability |
|
|
|
Nov. 10 |
More on reduction proofs |
|
|
Rice’s Theorem |
|
|
|
Nov. 17 |
Reduction proofs for nonsemidecidability |
|
|
Other undecidable
problems |
|
|
|
The Chomsky hierarchy |
|
|
|
Nov. 24 |
Introduction to complexity
theory |
|
|
Measuring time and space
complexity |
|
|
|
P and NP |
|
|
|
THANKSGIVING |
|
|
|
Dec. 1 |
Using reduction for
complexity |
|
|
The Cook-Levin Theorem |
|
|
|
Other NP-complete problems |
|