|
|
Schedule: CSE 3813 Introduction to Formal Languages and Automata,
Fall 2011
For the events and topics listed below, all of the dates are
tentative except for the final exam date. I will adjust this
schedule as the semester progresses.
| Week |
Class Dates |
Events |
Lecture Topics and Reading
Assignments |
| 1 |
Thu, Aug 18 |
|
Class Overview
1.1 Mathematical Preliminaries and Notation |
| 2 |
Tue, Aug 23 |
|
1.2 Three Basic Concepts
|
| Thu, Aug 25 |
Quiz 1 |
| 3 |
Tue, Aug 30 |
|
2.1 Deterministic Finite Acceptors
|
| Thu, Sep 1 |
Quiz 2 |
| 4 |
Tue, Sep 6 |
|
2.2
Nondeterministic Finite Acceptors
2.3
Equivalence of DFAs and NFAs
|
| Thu, Sep 8 |
Quiz 3 |
| 5 |
Tue, Sep 13 |
|
3.1
Regular
Expressions
|
| Thu, Sep 15 |
no class — game day
|
| 6 |
Tue, Sep 20 |
Quiz 4 |
3.2
Connection between REs and RLs
|
| Thu, Sep 22 |
|
| 7 |
Tue, Sep 27 |
|
3.3
Regular Grammars |
| Thu, Sep 29 |
Midterm I |
| 8 |
Tue, Oct 4 |
Jeff Lieberman talk*
|
4.1 Closure Properties of Regular Languages |
| Thu, Oct 6 |
|
| 9 |
Tue, Oct 11 |
|
4.3 Identifying Non-regular Languages
5.1 Context-Free Grammars
|
| Thu, Oct 13 |
Quiz 5 |
| 10 |
Tue, Oct 18 |
|
7.1
Nondeterministic
Pushdown Automata
|
| Thu, Oct 20 |
Quiz 6 |
| 11 |
Tue, Oct 25 |
|
7.3 DPDAs
and DCF Languages
9.1
The
Standard Turing Machine
|
| Thu, Oct 27 |
|
| 12 |
Tue, Nov 1 |
|
9.2
Combining
Turing Machines |
| Thu, Nov 3 |
Midterm II |
| 13 |
Tue, Nov 8 |
|
9.3 The Church-Turing Thesis
10.1
Minor Variations on TMs
|
| Thu, Nov 10 |
|
| 14 |
Tue, Nov 15 |
|
10.2
Complex Variations on TMs
10.3 Nondeterministic TMs
10.4
The Universal TM |
| Thu, Nov 17 |
Quiz 7 |
| |
Tue, Nov 22 |
no class — Thanksgiving |
|
| Thu, Nov 24 |
no class — Thanksgiving |
| 15 |
Tue, Nov 29 |
|
|
| Thu, Dec 1 |
Quiz 8 |
| 16 |
Mon, Dec 5 |
Final Exam |
12 – 3 pm, Butler 104 |
*Jeff Lieberman is speaking at 7pm, Oct 4th, in the Coliseum. If you attend, swipe your student ID card at the door, and I will give you 20 bonus quiz points (this is half of a quiz grade!). He is a Hearin Distinguished Lecturer, and it should be cool!
Last Modified:
August 06, 2012
|