Class | Topic | Linz | Homework | Exam |
---|---|---|---|---|
1: Tue Jan 17 |
Introduction | Sections 1.1-2 | ||
2: Thu Jan 19 |
DFAs | Section 2.1 | ||
3: Tue Jan 24 |
NFAs | Section 2.2 | ||
4: Thu Jan 26 |
Manipulating FAs | Sections 2.3-4 |
#1 due over weekend |
|
Tue Jan 31 |
Class canceled | |||
5: Thu Feb 2 |
Regular Expressions | Section 3.1 |
#2 due over weekend |
|
6: Tue Feb 7 |
Conversions between FAs and Regular Expressions |
Section 3.2 | ||
7: Thu Feb 9 |
Regular Languages | Sections 4.1-2 (+ 3.3) |
#3 due over weekend |
|
8: Tue Feb 14 |
Non-Regular Languages | Sections 4.3 | ||
9: Thu Feb 16 |
Wrap up (Non)Regular Languages |
#4 due over weekend |
||
10: Tue Feb 21 |
Context-Free Grammars (CFGs) | Sections 5.1&3 | ||
11: Thu Feb 23 |
Examples of CFGs Review session |
|||
12: Tue Feb 28 |
Exam #1 | |||
13: Thu Mar 2 |
Ambiguity of CFGs | Section 5.2 |
#5 due over weekend |
|
14: Tue Mar 7 |
Transformations on CFGs | Sections 6.1-2 | ||
15: Thu Mar 9 |
Wrap up CFGs | Section 6.3 | #6 due over Spring break |
|
16: Tue Mar 21 |
Pushdown Automata (PDA) | Section 7.1 | ||
17: Thu Mar 23 |
Convert between PDAs and CFGs Deterministic PDAs |
Section 7.2 Section 7.3 |
#7 due over weekend |
|
18: Tue Mar 28 |
Pumping Lemma for Context-Free Languages (CFLs) |
Section 8.1 | ||
19: Thu Mar 30 |
Closure Properties of CFLs | Section 8.2 | #8 due over weekend | |
20: Tue Apr 4 |
Wrap up CFGs and CFLs | |||
21: Thu Apr 6 |
Compilers LL parsing |
Chapter 15 Chapter 16 |
||
22: Tue Apr 11 |
Exam #2 | |||
23: Thu Apr 13 |
Wrap up LL parsing
Motivate LR parsing |
Chapter 16 |
#9 due over weekend |
|
24: Tue Apr 18 |
LR parsing | Chapter 17 summarized in uploaded notes |
||
25: Thu Apr 20 |
Turing Machines | Chapter 9 |
#10 due over weekend |
|
26: Tue Apr 25 |
TMs, Variations Stack/Counter Machines |
Section 10.1 | ||
27: Thu Apr 27 |
MultiTape TMs Nondeterministic TMs Universal TM Recursive/RE languages |
Section 10.2 Section 10.3 Section 10.4 Section 11.1 |
#11 due over weekend |
|
28: Tue May 2 |
Undecidability (770 only) | Chapter 12 | ||
29: Thu May 4 |
Review session | |||
Mon May 8 |
Final Exam 2:00--3:50pm |