CS341 Automata Theory
Elaine Rich
Schedule of Classes
|
Week |
Topics |
|
|
Jan. 15 |
The big picture |
|
|
What is a language? |
|
|
|
Finite state machines |
|
|
|
Jan. 22 |
Nondeterministic finite state machines |
|
|
Finite state transducers |
|
|
|
Jan. 29 |
HMMs and their applications |
|
|
Regular expressions |
|
|
|
Equivalence of regular expressions and FSMs |
|
|
|
Feb. 5 |
Closure properties of regular languages |
|
|
Regular Pumping Theorem |
|
|
|
Decision procedures for regular languages |
|
|
|
Feb.12 |
Review of regular languages |
|
|
Context-free grammars |
|
|
|
Feb. 19 |
Manipulating context-free grammars |
Tuesday evening: Midterm 1 |
|
Parse trees |
|
|
|
Ambiguity |
|
|
|
Feb.26 |
Pushdown automata |
|
|
Equivalence of PDAs and CFGs |
|
|
|
March 4 |
Context-Free Pumping Theorem |
|
|
Closure properties of context-free languages |
|
|
|
Decision procedures for context-free languages |
|
|
|
March 11 |
SPRING BREAK |
|
|
March 18 |
Turing machines |
|
|
Multiple tapes and nondeterminism |
|
|
|
Simulating real computers |
|
|
|
The Universal Turing machine |
|
|
|
March 25 |
Church’s Thesis |
Tuesday evening: Midterm 2 |
|
Other computational models |
|
|
|
The unsolvability of the halting problem |
|
|
|
April 1 |
Decidable and semidecidable languages |
|
|
Reduction proofs for undecidability |
|
|
|
April 8 |
Rice’s Theorem |
|
|
More on reduction proofs |
|
|
|
April 15 |
Reduction proofs for nonsemidecidability |
|
|
Other undecidable problems |
|
|
|
April 22 |
The Chomsky Hierarchy |
|
|
Introduction to complexity theory |
|
|
|
P and NP |
|
|
|
April 29 |
Using reduction for complexity |
|
|
The Cook-Levin Theorem |
|
|
|
Other NP-complete problems |
|