CS81:  Computability and Logic -- Part II

Fall 2007

Date Topic Assigment Links
Tues
11/6/07		 Regular Languages cont.
Myhill-Nerode Theorem
Pumping Lemma
Decision problems for regular languages
HW 7 Solution to HW6
Thurs
11/8/07		 Context Free Languages
Context free grammars
Push down automaton
   
Tues
11/13/07		 Context free languages cont.
Parsing
 HW 8 Solutions to HW 7
Thurs.
11/15/07		 Context free languages cont.
Pumping lemma
    
Tues
11/20/07		 Context free languages cont. HW 9 Solutions to HW 8
Thurs
11/22/07		 Thanksgiving break    
Tues
11/27/07		 Parsing HW 10 Solutions to HW 9
Thurs
11/29/07		 Turing machines    
Tues
12/4/07		 Recursive functions HW 11 Solutions to HW 10
Thurs
12/6/07		 Rice's theorem    
Tues
12/11/07		 Lambda calculus    
Thurs
12/13/07		 Review   Solutions to HW 11