CS341H Automata Theory
- Honors
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 |
|
|
|
HMMs and their applications |
|
|
|
Jan. 29 |
Büchi automata |
|
|
Regular expressions |
|
|
|
Equivalence of regular expressions and FSMs |
|
|
|
Regular grammars |
|
|
|
Feb. 5 |
Closure properties of regular languages |
|
|
Regular Pumping Theorem |
|
|
|
Decision procedures for regular languages |
|
|
|
Feb.12 |
Context-free grammars |
|
|
Parse trees |
|
|
|
Ambiguity |
|
|
|
Feb.19 |
Grammars and normal forms |
Tuesday evening: Midterm 1 |
|
Pushdown automata |
|
|
|
Equivalence of PDAs and CFGs |
|
|
|
Feb. 26 |
Context-Free Pumping Theorem |
|
|
Closure properties of context-free languages |
|
|
|
March 4 |
Deterministic context-free languages |
|
|
Parikh’s Theorem |
|
|
|
Decision procedures for context-free languages |
|
|
|
Turing machines |
|
|
|
March 11 |
SPRING BREAK |
|
|
March 18 |
Multiple tapes and nondeterminism |
|
|
Simulating real computers |
|
|
|
The Universal Turing machine |
|
|
|
Church’s Thesis |
|
|
|
Other computational models |
|
|
|
The unsolvability of the halting problem |
|
|
|
March 25 |
Decidable and semidecidable languages |
Tuesday evening: Midterm 2 |
|
Reduction proofs for undecidability |
|
|
|
April 1 |
Rice’s Theorem |
|
|
Reduction proofs for nonsemidecidability |
|
|
|
April 8 |
Other undecidable problems |
|
|
Context-sensitive languages |
|
|
|
The Chomsky hierarchy |
|
|
|
April 15 |
Introduction to complexity theory |
|
|
Review of asymptotic dominance |
|
|
|
Measuring time and space complexity |
|
|
|
P and NP |
|
|
|
April 22 |
Using reduction for complexity |
|
|
NP-completeness and the Cook-Levin Theorem |
|
|
|
Other NP-complete problems |
|
|
|
April 29 |
Space complexity |
|
|
Practical solutions for hard problems |
|