Comp Sci 2MJ3: Theory of Computation
Fall 2006

• Instructor: Michael Soltys, email: my last name at mcmaster.ca
• Course Information
• Time: classes on M,W 11:30-12:20, and F 13:30-14:20, in BSB/104, and tutorial on T 8:30-9:20, in BSB/B154B.
• Course outline: Models of computation: finite automata, regular expressions, context-free grammars, push-down automata, and Turing machines. Relationships between these models (e.g., finite automata are equivalent to regular expressions). Determinism and non-determinism in computations, and quantum computers. Limitations of the different models (e.g., Pumping Lemma for showing that a language is not regular, and the Halting Problem). Recursive and recursively enumerable languages, Rice's theorem. Feasible problems, intractable problems, and the complexity classes P and NP.
• Textbook: Introduction to the Theory of Computation, 2nd Edition, by Michael Sipser:
  
  Book's web site
• Check this web page regularly for announcements.
• Previous versions of this course: 2005. Note that this course was taught before as a Software Engineering course.
• Please Read: McMaster Academic Integrity Statement.

Announcements:

• Nov 17: Test 4 will take place on Friday November 24 as scheduled. The test will be on chapter 5, sections 1 and 2 (section 2 is just one short result, so I will present it on Monday). On Tuesday (during the tutorial) and on Wednesday (during the lecture), we are going to review for Test 4. During the last week of classes will do section 5.3, which will be tested on the final exam. The questions relevant for Test 4 are posted below.
• Nov 15: Test 3 with solutions has been posted below.
• Oct 27: Exercises for chapter 3 posted below.
• Oct 22: Since Greg gave two tutorials this week (in preparation for Test 2), there will be no tutorial on Tuesday Oct 24. Test 2 with solutions has been posted below.
• Oct 16: CFLs are not closed under interesection, but we'll have to wait until chapter 5 to prove it.
• Oct 12: The problems for chapter 2 have been posted below. Remember you must also do all the exercises, to prepare for the test on Friday Oct 20.
• Oct 2: Test 1 with solutions has been posted below.
• Sept 29: Test 1 is rescheduled for Monday October 2, at 11:30-12:20, in BSB/104 (the usual classroom, the usual Monday lecture time)
• Sept 25: The first test is coming up this Friday (Sept 29). Make sure you know how to do the exercises listed below.
• Sept 14: Test dates:
  • Test 1: Monday Oct 2 (originally scheduled for Friday Sept 29)
  • Test 2: Friday Oct 20
  • Test 3: Friday Nov 10
  • Test 4: Friday Nov 24
  The tests will be written in the usual lecture room (BSB/104). Also note that the tests are every 3 weeks, except the last two tests are 2 weeks apart (due to the test ban).
• The first two lectures, Friday September 8, and Monday September 11, will be taught by Greg Herman.

Exercises:

Each chapter in Sipser has a set of exercises (to test basic understanding of the material), and problems (to develop problem solving skills in the area). You must do all the exercises, but only the problems listed below. Remember that the problems on the tests will be based on the problems in Sipser.

Test 1	Chp 0: 0.12,0.13	Chp 1: 1.31--1.39	Chp 1: 1.51, 52 (Myhill-Nerode Thm) 1.53, 1.54
Test 2	Chp 2: 2.18,19,21-24,26,30,31,35
Test 3	Chp 3: 3.9-20	Chp 4: 4.9-28
Test 4	Chp 5: 5.1-3,8,5.9-15,5.17-20.

Tests:

• Test 1 with solutions
• Test 2 with solutions
• Test 3 with solutions
• Test 4 with solutions