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, 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, 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 200405 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 (9096), 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
6289. 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
ABBB163 during the usual lecture time (9:3010:20), as usual.
 Nov 12: Latest slides (5261) 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 ContextFree languages: chapters 5,6,7. The
corresponding exercises are listed below. Remember that the test will
be written in the test room, ABBB163, 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 3539 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:305:20.
 Sep 30: Problem Set 2 has been posted below.
 Sep 29: Latest slides have been posted below.
 Sep 27: Test 1 Marking Scheme:
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:3012:20 office hours have been moved to 4:305:20 in ITB222 (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:3011:20 in ITB214
 Tim Paterson (TA): Thursdays, 4:305:20 in
ITB222 (No tutorial on Oct 14th)
 Liuxing Kan (TA): Wednesdays, 3:304:20 in ITB240
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 ABBB163.
 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:
 Exercises:
Chp2 
Chp 3 
Chp 4 
Chp 5 
Chp 6 
Chp 7 
Chp 8 
Chp 9 
Chp 10 

3.1.15 
4.1.14 
5.1.18 
6.1.1 
7.1.16,810 

9.1.14 
10.1.13,57 

3.2.16,8 
4.2.110 
5.2.14 
6.2.18 
7.2.14 
8.2.15 
9.2.16 
10.2.12 

3.4.15 
4.3.15 
5.3.13 
6.3.17 
7.3.17 
8.3.13 
9.3.17 


4.4.12 
5.4.17 
6.4.14 
7.4.15 
8.4.19 
9.4.13 







9.5.1,2
