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