Comp Sci 2MJ3: Theory of Computation
Fall 2009
 Instructor: Michael Soltys, email:
my last name at mcmaster.ca
 Course Outline
(Revised on September 16, 2009)
 Time: lectures on Tu, Th, Fr, 14:3015:20, in
ABB/136 (starting Friday September 18,
all lectures
will be in ITB137), and tutorials:
 T01: Mo, 11:3013:20, JHE/210
 T02: We, 11:3013:20, HH/102
 Course outline: Models of computation: finite
automata, regular expressions, contextfree grammars, pushdown
automata, and Turing machines. Relationships between these models
(e.g., finite automata are equivalent to regular expressions).
Determinism and nondeterminism in computations.
 Textbook:
Models of Computation: An introduction to computability theory,
by Maribel Fernandez:
 Check this web page regularly for announcements.
 Previous versions of this course:
2006.
 Please Read:
McMaster Academic Integrity Statement.
Announcements:
 Dec 2: Test 3 with solutions has been posted below.
 Nov 24: Here are the
slides on primitive recursive functions.
 Nov 24: Solutions and comments to assignment 3 have been posted
below.
 Nov 15: Some clarifications for assignment 3. First, in
question 1 we have functions f,g,h, even though we have used those
function names in the definition of primitive recursion; to avoid
confustion you can rename g(x,y) as sum(x,y) and rename h(x,y) as
prod(x,y). Also, rename f(x,z) to q(x,z). Doing this is not strictly
necessary, but it might help you not to become confused with the f,g,h
function names in the definition of primitive recursion. The inverted
horseshoe in question 2 (i.e., the superset symbol) is logical
implication; you might be more familiar with the rightarrow for
logical implication. (Thanks to Nicholas James for pointing out those
possible pitfalls.)
 Nov 9: Assignment 3 (due Nov 20) has been posted below. Also,
Test 2, together with its solutions, has been posted below.
 Nov 6: Solutions (with comments) to Assignment 2 have been posted
below.
 Oct 30: The document on relations
has been slightly updated. In particular theorem B.4 has been
restated so that we have the identity (id) function on all of X,
rather than just over the domain of R. Same change in theorem B.9.
Equation (B.2) has also been changed with a new definition of id
(again, over X, rather than the domain of R). Lemma B.15 has been
updated as well. These changes are due to Nicholas James and Michael
Hebelka.
 Oct 28: Nicholas James has written a very complete set of
comments to test 1; you must read them!
 Oct 25: Notes on relations. We
started talking about relations last week, and we are going to finish
on Tuesday.
 Oct 20: Assignment 2 has been posted below; it is due on October
30.
 Oct 20: The Wednesday tutorials have been eliminated, and instead
there will be an extra hour of office time on Mondays. Thus, the new
office hours will be: Mondays, 11:3013:30 in JHE/210.
 Oct 20: Solutions to Test 1 have been posted below.
 Oct 15: Notes on PDAs by Nicholas James.
 Oct 14: Assignment 1 comments by Nicholas James have been posted below.
 Oct 10: The lecture on Friday October 9 was given by Ariel
Fernandez, who conducted a review for Test 1. Ariel was asked to
prepare for the web one of the problems that he did not have time to
cover in the lecture; he has kindly done so:
Sipser 3.11.
 Oct 6: The Monday October 12 and Wednesday October 14 tutorials
will be replaced by a single tutorial on Thursday October 15
during the usual lecture time. This tutorial is scheduled in
preparation for Test 1 which will take place on October 16, again
during the usual lecture time.
 Oct 1: Here are notes by Nicholas James on
how to make M' from M such that L(M')=L(M)*
 Sept 21: Instructor's office hours:
 Tuesdays 1:302:30
 Thursdays 1:302:30
Or by appointment.
 Sept 19: Assignment 1 has been posted below.
 Sept 19: Dates for assignments and tests:
Assignment 1  October 2

Test 1  October 16

Assignment 2  October 30

Test 2  November 6

Assignment 3  November 20

Test 3  November 27 
updated on Oct 5

All tests will be written during the usual lecture hour in ITB137
(which is the usual lecture room). The dates for the assignments
indicate the due dates; the assignments will typically be given at
least two weeks before the due date. Assignments are to be submitted
during the lecture on the due date.
 Sept 18: The tutorials on Monday Sept 21 & Tuesday Sept 22 are
canceled because the TA is sick. Tutorials
will start therefore on September 28. Please email the TA if you have
any questions or need help; the TA is Nicholas James, and his email is
jamesnd2 at mcmaster dot ca.
 Sept 16: Starting Friday September 18, all lectures
will be in ITB137
 Sept 14: The lecture on Tuesday September 15 will be given by Tim
Paterson. It will be a review of mathematical induction, which
we are going to be using in the course.
 The TA will hold the following office hours:
 Mo, 11:3012:30 in JHE/210
 Wed, 11:3012:30 in HH/102
Assignments and Tests: