SE 4I03: Theoretical Foundations of Computation
Fall 2004

• Instructor: Michael Soltys, email: my last name at mcmaster.ca
• Course Information
• 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 Automata Theory, Languages, and Computation, by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, SECOND EDITION:
  
• Check this web page regularly for announcements. Some documents will be available in PostScript; if you need a PostScript previewer, go to Ghostview Software.
• Previous versions of this course: 2001, 2002, 2003.
• Please Read: McMaster Academic Integrity Statement.

Announcements:

• June 13, 2005: Click here for the 2004-05 deferred exam.
• Dec 20: The final exam has been posted below.
• Dec 8: Click here to see your term marks. They are displayed by student number only. Please let me know if there are discrepancies. (I may ask you to see the relevant test.)
• Nov 30: The last batch of slides (90--96), and the exercises for chapter 10, have been posted below. In chapter 10, you are only responsible for sections 10.1 and 10.2.
• Nov 29: Click here for Tim Patereson's marking scheme for Test 4. (Questions 3,4,5). Click here for Liuxing Kan's marking scheme (Questions 1,2).
• Nov 26: Test 4 with solutions has been posted below.
• Nov 23: On Friday Dec 3, instead of the usual lecture, Tim Paterson is going to go over the exam from last year (in the usual classroom, at the usual time). Tim's Thursday tutorial will take place as usual. If you want, you can bring the exam to class on Dec 3; click here for a copy of the 2003 exam.
• Nov 18: The exercises for chapter 9 have been posted below.
• Nov 17: A large batch of slides has been posted below; slides 62--89. These slides will be covered in the next few lectures, and they are part of the material that will appear on Test 4. Test 4 includes chapters 8 and 9, and it will take place on Friday Nov 26, in ABB-B163 during the usual lecture time (9:30--10:20), as usual.
• Nov 12: Latest slides (52--61) have been posted below.
• Nov 10: Click here for Tim Patereson's marking scheme for Test 3. (Questions 3,4,5,6). Click here for Liuxing Kan's marking scheme (Questions 1,2).
• Nov 9: Test 3 with solutions has been posted below.
• Nov 4: Note on exercise 6.3.4, item 3 d(q,1,X)={(q,X)}. Using the formula at the bottom of page 242, this should become the set of rules:
  • [qXq]-->1[qXq]
  • [qXp]-->1[qXp]
  because we build it on the template [qX(r1)]-->a[r(Y1)(r1)], where (Y1)=X, and r=1, so we only have a choice for (r1) which ought to be each of the states, but there are only two states: {q,p}.
• Oct 28: Test 3 will take place on Friday Nov 5, as scheduled. It will be on Context-Free languages: chapters 5,6,7. The corresponding exercises are listed below. Remember that the test will be written in the test room, ABB-B163, during the usual lecture time.
• Oct 28: The slides and the assigned exercises are shown in a table (below) for better readability.
• Oct 25: Exercises for chapter 6 (Problem Set 5) are posted below.
• Oct 21: Slides 35-39 have been posted below, as well as the exercises for chapter 5 (Problem Set 4).
• Oct 19: The latest slides have been posted below.
• Oct 19: Test 2 with solutions has been posted below. Click here for Tim Patereson's marking scheme (Questions 4,5). Click here for Liuxing Kan's marking scheme (Questions 1,2,3).
• Oct 7: Test 2 (Oct 15) will cover chapters 3 (Reg Exp) and 4 (Properties of Reg Lang). See below for the corresponding exercises.
• Oct 5: Important: The Oct 14 tutorial was originally cancelled (there was a test written in the usual classroom at that time), but as it falls right before Test 2, it has been reinstated, and it will take place in ABB/164 at 4:30-5:20.
• Sep 30: Problem Set 2 has been posted below.
• Sep 29: Latest slides have been posted below.
• Sep 27: Test 1 Marking Scheme:
  • Liuxing's comments on Q1 & Q3
  • Tim's comments on Q2 & Q4
  Make sure that you read these comments carefully before going to the office hours to discuss your mark with the TAs!
• Sep 24: Test 1 with solutions has been posted below.
• Sep 22: Important notice: Due to popular demand, the Thursday 11:30-12:20 office hours have been moved to 4:30-5:20 in ITB-222 (same day). Because of the room restrictions, there will be no Thursday tutorial on Oct 14th.
• Sep 15: Office hours:
  • Michael Soltys (Instructor): Wednesdays, 10:30-11:20 in ITB-214
  • Tim Paterson (TA): Thursdays, 4:30-5:20 in ITB-222 (No tutorial on Oct 14th)
  • Liuxing Kan (TA): Wednesdays, 3:30-4:20 in ITB-240
  If you have questions regarding the material (or marking concerns), you should always meet with the TAs first.
• Sep 1: The tests will take place on the following Fridays:
  • Sep 24
  • Oct 15
  • Nov 5
  • Nov 26
  The test room (for all four dates) will be ABB-B163.
• Sep 1: The course information sheet has been posted above. It will be handed out on the first day of class (Sep 10, in ABB/165).

Tests, slides, and suggested exercises:

• Test 1
• Test 2
• Test 3
• Test 4
• Final Exam
• Slides:

  1-6

  7-8

  9-11

  12-17

  18-20

  21-30

  31-34

  35-39

  40-48

  49-51

  52-61

  62-89

  90-96

• Exercises:

  Chp2	Chp 3	Chp 4	Chp 5	Chp 6	Chp 7	Chp 8	Chp 9	Chp 10
  	3.1.1--5	4.1.1--4	5.1.1--8	6.1.1	7.1.1--6,8--10		9.1.1--4	10.1.1--3,5--7
  	3.2.1--6,8	4.2.1--10	5.2.1--4	6.2.1--8	7.2.1--4	8.2.1--5	9.2.1--6	10.2.1--2
  	3.4.1--5	4.3.1--5	5.3.1--3	6.3.1--7	7.3.1--7	8.3.1--3	9.3.1--7
  		4.4.1--2	5.4.1--7	6.4.1--4	7.4.1--5	8.4.1--9	9.4.1--3
  							9.5.1,2