| Wk |
Day |
Date |
Topic |
Reading |
Homework |
| 1 |
M |
Aug 28 |
Math review |
1.1 |
1.1: 1, 4, 6, 9, 10, 12, 13, 14, 17(a), 19, 23, 25, 31, 33-35 |
| |
T |
Aug 29 |
Proof techniques |
|
|
| |
W |
Aug 30 |
Automata, Languages, and Grammars |
1.2 - 1.3 |
1.2: 2-5, 7, 11-13, 14(b)-(g), 15(a)-(b), 16, 17, 18(b), 21-23 |
| |
F |
Sep 1 |
DFA's |
2.1 |
2.1: 2-6, 7(a)-(c), 9(a)-(d), 11, 12, 16, 21, 22, 25 |
| 2 |
M |
Sep 4 |
DFA's |
|
|
| |
T |
Sep 5 |
NFA's |
2.2 |
2.2: 2-4, 7, 9, 12, 13, 18, 21 |
| |
W |
Sep 6 |
Equivalence of DFA's and NFA's |
2.3 |
2.3: 1, 3, 5, 7, 8, 12, 13 |
| |
F |
Sep 8 |
Regular expressions |
3.1 |
3.1: 1-5, 7, 9, 15, 16(e), 21, 24, 26, 27 |
| 3 |
M |
Sep 11 |
Equivalence of regular expressions and regular languages |
3.2 |
3.2: 1, 3, 4, 8, 10, 11, 15 |
| |
T |
Sep 12 |
Equivalence of RE and RL, cont. |
|
|
| |
W |
Sep 13 |
Regular Grammars |
3.3 |
3.3: 1-4, 8, 9, 11, 16 |
| |
F |
Sep 15 |
Closure properties of regular languages |
4.1 |
4.1: 1 (prove the iff), 2, 3, 6, 9, 10, 16, 26 |
| 4 |
M |
Sep 18 |
Review for exam |
|
|
| |
T |
Sep 19 |
Elementary questions about regular languages |
4.2 |
4.2: 2, 3, 5, 6, 7, 8, 15 |
| |
W |
Sep 20 |
Exam 1 (Chapters 1-3) |
|
|
| |
F |
Sep 22 |
Pumping lemma for regular languages |
4.3 |
4.3: 3, 4(b), 4(e), 4(f), 5(a), 5(d), 7, 10 ((a) for extra credit), 15(a)-(d) |
| 5 |
M |
Sep 25 |
More pumping lemma proofs |
|
|
| |
T |
Sep 26 |
Context-free grammars |
5.1 |
5.1: 1, 2, 6 (write entire proof of Thm. 5.1), 7(b)-(c), 8(b)-(d), 19, 21, 23, 27 |
| |
W |
Sep 27 |
Parsing and Ambiguity |
5.2-5.3 |
5.2: 1, 2, 5-7 |
| |
F |
Sep 29 |
No class (Miami U. trip) |
|
|
| 6 |
M |
Oct 2 |
Transformations of context free grammars |
6.1 |
6.1: 5-9 |
| |
T |
Oct 3 |
Transformations, cont. |
|
|
| |
W |
Oct 4 |
Normal forms for context free grammars |
6.2 |
6.2: 2-5, 9-11 |
| |
F |
Oct 6 |
CYK membership algorithm |
6.3 |
6.3: 1, 2 |
| 7 |
M |
Oct 9 |
Nondeterministic Pushdown acceptors |
7.1 |
7.1: 1, 2, 3(a), 4(a,c,d,f,i,j), 6, 10, 17 |
| |
T |
Oct 10 |
NPDA examples and Review |
|
|
| |
W |
Oct 11 |
NPDA examples and Review |
|
|
| |
F |
Oct 13 |
Exam 2 (Chapters 4-6) |
|
|
| 8 |
M |
Oct 16 |
Constructing NPDA's from CFG's |
7.2 |
7.2: 4-7, 11-12, 15, 18 |
| |
T |
Oct 17 |
Constructing CFG's from NPDA's |
7.2 |
|
| |
W |
Oct 18 |
An example of the construction |
|
|
| |
F |
Oct 20 |
Deterministic PDA's and CFL's |
7.3-7.4 |
|
| 9 |
M |
Oct 23 |
Pumping lemma for CFL's |
8.1 |
|
| |
T |
Oct 24 |
Pumping lemma for linear languages |
8.1 |
8.1: 1, 2, 7(a)-(c), 8(a)-(c), 11-13 |
| |
W |
Oct 25 |
Closure properties and decision algorithms for CFL's |
8.2 |
8.2: 3, 5, 11 |
| |
F |
Oct 27 |
Turing machines |
9.1 |
|
| 10 |
M |
Oct 30 |
Turing machines |
|
9.1: 7(e), 8-10, 11(b), 11(e), 17 |
| |
T |
Oct 31 |
No class |
|
|
| |
W |
Nov 1 |
Turing machines |
|
|
| |
F |
Nov 3 |
Church-Turing Thesis |
9.2-9.3 |
|
| 11 |
M |
Nov 6 |
Alternative Turing machines |
10.1 |
10.1: 2, 4, 8 |
| |
T |
Nov 7 |
Turing machines with multiple tapes |
10.2 |
10.2: 4, 5 |
| |
W |
Nov 8 |
Review for exam |
|
|
| |
F |
Nov 10 |
Exam 3 (Chapters 7-9) |
|
|
| 12 |
M |
Nov 13 |
Other variations of TM's and a universal TM |
10.3-10.5 |
|
| |
T |
Nov 14 |
Recursive and recursively enumerable languages |
11.1 |
|
| |
W |
Nov 15 |
|
|
|
| |
F |
Nov 17 |
|
|
|
| |
|
Nov 20-24 |
Thanksgiving Break |
|
|
| 13 |
M |
Nov 27 |
Recursive and RE languages, cont. |
|
|
| |
T |
Nov 28 |
Unrestricted grammars |
11.2 |
11.2: 1, 2, 6 |
| |
W |
Nov 29 |
The halting problem |
12.1 |
12.1: 1, 3, 5, 9 |
| |
F |
Dec 1 |
More undecidable problems |
12.1, 12.2 |
|
| 14 |
M |
Dec 4 |
Recursive functions |
13.1 |
|
| |
T |
Dec 5 |
|
|
|
| |
W |
Dec 6 |
Exam 4 (Chapters 10-12.2, 13.1) |
|
|
| |
F |
Dec 8 |
|
|
|
