Text: Introduction to the Theory of Computation by Michael Sipser, PWS Publishing Company
Syllabus: Regular Languages, Context-Free Languages, Turing Machines, Decidability ( that is, the first four chapters of the book but with strong emphasis on regular languages)
Highly Recommended: Introduction to Automata Theory, Languages, and Computation (first edition), John E. Hopcroft, Jeffrey D. Ullman, Addison-Wesley Publishing Company. This is a very advanced textbook and it covers a lot of the research literature till 1979. I will refer to this book for regular grammers and Goedel numbers for Turing machine
Office Hours: W 1-2:30 pm
TA: Kuo -Chieh Ting PGH 526 , Office Hours: 4:00-5:00pm T, TH e-mail:kcting@cs.uh.edu
Grading: There will be four tests. The three highest scores count 60% and the Final counts 40% for your final grade.
Tests:
Test 1: Thursday, February 7
Test 2: Thursday, March 14
Test 3: Tuesday, April 9
Test 4:TBA
Final: Tuesday, May 7 2-5 p.m. You need to bring a picture ID.
Homework:
01/24/02: 1.1-1.3 , 1.4 (a-d)
01/31/02: 1.4 (e-n), 1.5, 1.6, 1.12
02/14/02: 1.7, 1.8, 1.9, 1.23, 1.24
02/14/02: 1.14, 1.15, 1.16,
03/04/02: 1.17(a), 2.3, 2.4, 2.6 (a)
03/26/02: 2.1, 2.3, 2.4, 2.6(a), 2.14, 2.18 (a)
04/11/02: 3.1, 3.2,3.5,3.7; find a TM for L={0*1*} and L={0^n1^n}