CS341 Automata Theory
Elaine Rich
Schedule of Classes
|
Week |
Topics |
|
|
Jan. 17 |
Why study
automata theory? |
|
|
Problems as
languages |
|
|
|
Roadmap to the
theory we will build |
|
|
|
Finite
state machines |
|
|
|
Jan. 24 |
Finite
state machines, continued |
|
|
Nondeterministic
finite state machines |
|
|
|
Jan. 31 |
Finite
state transducers |
|
|
Stochastic
FSMs |
|
|
|
Regular
expressions |
|
|
|
Equivalence
of regular expressions and FSMs |
|
|
|
Feb. 7 |
Closure
properties of regular languages |
|
|
Regular
Pumping Theorem |
|
|
|
Feb.14 |
Functions
on regular languages |
|
|
Decision
procedures for regular languages |
|
|
|
Review of regular
languages |
|
|
|
Context-free
grammars |
|
|
|
Feb. 21 |
Manipulating
context-free grammars |
Tuesday
evening: Midterm 1 |
|
Parse trees |
|
|
|
|
Ambiguity |
|
|
Feb. 28 |
Pushdown
automata |
|
|
Equivalence
of PDAs and CFGs |
|
|
|
March 6 |
Context-Free
Pumping Theorem |
|
|
Closure
properties of context-free languages |
|
|
|
Decision
procedures for CF languages |
|
|
|
March 13 |
SPRING
BREAK |
|
|
March 20 |
Turing
machines |
|
|
Multiple
tapes and nondeterminism |
|
|
|
March 27 |
Simulating
real computers |
|
|
The
Universal Turing machine |
|
|
|
|
Church’s
Thesis |
|
|
|
Other
computational models |
|
|
|
The unsolvability of the halting problem |
|
|
|
Decidable
and semidecidable languages |
|
|
April 3 |
Reduction
proofs for undecidability |
Tuesday
evening: Midterm 2 |
|
April 10 |
More on
reduction proofs |
|
|
Rice’s
Theorem |
|
|
|
April 17 |
Examples of
practical consequences |
|
|
Reduction
proofs for nonsemidecidability |
|
|
|
April 24 |
Other undecidable problems |
|
|
|
The Chomsky
Hierarchy |
|
|
May 1 |
Introduction
to complexity |
|
|
|
P and NP |
|
|
|
NP-complete
problems |
|