Week  Dates 
Topics  Assignments 
1  Jan 25, 29  Course goals Course outline
Text Chapters 1, 2. 
homework 1 due Friday Jan 29 in class. 
2  Feb 1, 5

Math background Regular Expressions Text chapters 3, 4 Supplemental materials 
homework 2 due Friday Feb 5 in class. 
2  Feb 8, 12 
Supplemental materials:
Pattern Matching Lab

Pattern matching homework. relabSol.py: The solution to the homework, courtesy of R.B. Axtell. Due Friday Feb 12 in class But don't wait intil Feb 11 to start this. 
4  Feb 15, 19

Text chapters 4, 5
Regular Expressions Finite Automata 
homework 3: 
5  Feb 24, 26 
Text Chapters 6, 7 transistion Graphs Kleene's Theorem 
homework 4: due Feb 26 in class Don't leave this hw to the last minute. 
6  Mar 1, 5 
Text chapters 6, 7, 9,
transistion graphs Kleene's Theorem FA with Output 
homework 5a due Friday Mar 26 in class. 
7  Mar 8, 12 midterm handed out due Mar 10No Class Mar 12 
Text chapters 9, 10, 12
Regular Languages Pigeonhole principle, class notes, rough, Nonregular languages Decidability Reg expr that matches prime numbers 
No assignment over spring break. No Class Mar 12 
Mar 15, 19 
Spring 
Break.  
8  Mar 22, 26 
Text chapters 12, 13,14, 15
Contextfree languages Pushdown Automata 
homework 5b due Friday Mar 26 in class. 
9  Mar 29, April 2 
Text chapters 15, 16, 19
CFG = PDA non CF languages 
hw6 due Friday April 2 in class 
10  April 5, 9 
Text chapters 16, 19
Non CF Languages Turing Machines 
homework 7 due Friday April 9 in class. then, from now on homework: Students prepare for presentations 
11  April 12, 16 
Hw6 in class; turn in, in class. Turing Machines text, papers, web sites Lego Turing Machine A Hardware Working Turing machine Robot VW GTI Stanley and Stella 

12  April 19, 23 
Schedule student presentations text, papers, web sites Computability and halting video special topics 
April 23:
Student Presentations 
13  April 26, 30 
Student Presentations  April 26: Student Presentations  April 30: 