|
|
Schedule: CSE 3813 Introduction to Formal Languages and Automata,
Spring 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, Jan 6 |
|
Class Overview
1.1 Mathematical Preliminaries and Notation |
| 2 |
Tue, Jan 11 |
|
1.2 Three Basic Concepts
|
| Thu, Jan 13 |
Quiz 1 |
| 3 |
Tue, Jan 18 |
|
2.1 Deterministic Finite Acceptors
2.2
Nondeterministic Finite Acceptors
|
| Thu, Jan 20 |
Quiz 2 |
| 4 |
Tue, Jan 25 |
|
2.3 Equivalence of DFAs and NFAs
3.1 Regular
Expressions |
| Thu, Jan 27 |
Quiz 3 |
| 5 |
Tue, Feb 1 |
|
3.2
Connection between REs and RLs
3.3 Regular Grammars |
| Thu, Feb 3 |
Quiz 4 |
| 6 |
Tue, Feb 8 |
|
4.1 Closure Properties of Regular Languages |
| Thu, Feb 10 |
(no class – snow day) |
| 7 |
Tue, Feb 15 |
Midterm I
Neil deGrasse Tyson talk* |
4.3 Identifying Non-regular Languages |
| Thu, Feb 17 |
|
| 8 |
Tue, Feb 22 |
|
5.1 Context-Free Grammars
|
| Thu, Feb 24 |
Quiz 5 |
| 9 |
Tue, Mar 1 |
|
7.1
Nondeterministic
Pushdown Automata |
| Thu, Mar 3 |
|
| 10 |
Tue, Mar 8 |
|
7.2
PDAs and Context-Free Languages
7.3 DPDAs
and DCF Languages |
| Thu, Mar 10 |
Quiz 6 |
| |
Tue, Mar 15 |
|
(Spring Break) |
| Thu, Mar 17 |
|
| 11 |
Tue, Mar 22 |
|
9.1
The
Standard Turing Machine
9.2
Combining
Turing Machines
|
| Thu, Mar 24 |
|
| 12 |
Tue, Mar 29 |
|
9.3 The Church-Turing Thesis |
| Thu, Mar 31 |
Midterm II |
| 13 |
Tue, Apr 5 |
|
10.1
Minor Variations on TMs
10.2 Complex Variations on TMs |
| Thu, Apr 7 |
Quiz 7 |
| 14 |
Tue, Apr 12 |
|
10.3 Nondeterministic TMs
10.4
The Universal TM
|
| Thu, Apr 14 |
Quiz 8 |
| 15 |
Tue, Apr 19 |
|
11.1 Recursive and Recursively Enumerable Languages |
| Thu, Apr 21 |
|
| 16 |
Mon, Apr 25 |
Final Exam |
12 – 3 pm, Butler 103 |
*Neil deGrasse Tyson is speaking at 7pm, Feb 15th, 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!
Check out
A Cool Scientific American paper about Turning Machines (not
required reading)
Last Modified:
August 06, 2012
|