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