| Batch | Topic |
|---|
| 1 |
Introduction, fun, countability.
|
| 2 |
Alphabets, languages, DFAs beginning of NFA |
| 3 |
NFAs |
| 4 |
Regular expressions,
finite automata with output
Also available in postscript |
| 5 |
DFA closure properties and
decision algorithms |
| 6 |
DFA minimization part 1 |
| 7 |
DFA minimization part 2 |
| 8 |
DFA minimization part 3 |
| 9 |
DFA minimization part 4 |
| 10 |
CFGs definitions, language generated |
| 11 |
Grammar simplification,
Chomsky Normal Form |
| 12 |
Griebach Normal Form |
| 13 |
Pushdown Automata |
| 14 |
Equivalence of PDAs, CFGs |
| 15 |
CFL pumping lemma
|
| 16 |
CFL closure properties |
| 17 |
CFL decision algs, including
membership (CYK algorithm) |
| 18 |
Turing Machines definitions and examples |
| 19 |
TM programming tricks |
| 20 |
TM subroutines, k-tape TMs |
| 21 |
Nondeterministic TMs |
| 22 |
Church-Turing thesis; equivalence with RAMs |
| 23 |
Primitive and General Recursive Functions |
| 24 |
TMs as Generators |
| 25 |
Some closure properties of recursive and
r.e. languages |
| |
NEW ARRIVALS BELOW HERE: |
| 26 |
Decidability, Universal TMs, Halting Problem, Reductions.
See also Proof that Lu
is not recursive, and
Typical reduction template.
|
| 27 |
Rice's theorem.
|
| 28 |
Regular grammars, context-sensitive grammars,
unrestricted grammars, chomsky hierarchy.
|
| 29 |
Introduction to complexity theory.
|
| 30 |
Polynomial-time reductions.
|
| 31 |
NP-completeness.
|
