1 | Finite State Machines, Design, Non-Determinism |
2 | Closure Properties, Regular Expressions, Equivalence with Finite State Machines. |
3 | The Pumping Lemma – Proving a Language is Non-Regular, The Adversary Game, Using Closure Properties. |
4 | Regular Grammars, Equivalence to FSMs, Other FSM Variations, Minimization of FSM’s. |
5 | Decision Algorithms for Regular Sets and Undecidability |
6 | Context-Free Grammars, Semantic and Inductive Design, Examples, Applications. |
7 | Chomsky Normal Form. Three Applications. |
8 | Midterm |
9 | Pushdown Machines, Non-Determinism Adds Power, Equivalence to CFG’s. |
10 | The Pumping Lemma and Non-Context-Free Sets. |
11 | Closure Properties, DCFL’s and Decision Algorithms. |
12 | Turing Machines, Design. |
13 | Variations and Equivalence: Non-Determinism, MultiTape, Two-Way. |
14 | Recursive and Recursively Enumerable Sets, Undecidability. |