SE 4I03: Theoretical Foundations of Computation
Fall 2005
- 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 ABB/271, and tutorial on T 10:30-11:20, in
CNH/107.
- 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, using a different textbook:
2001,
2002,
2003,
2004.
- Please Read:
McMaster Academic Integrity Statement.
Announcements:
- Dec 14: The exam has been posted below.
- Dec 8: Tim Paterson is going to be holding office hours on
Friday Dec 9, 1-4, in a yet unknown room (Tim will post a note on his
office door (ITB-207) with directions).
- Dec 7: For chapter 7 you are responsible for all the exercises
and problems, including the *'ed ones, except for 7.35, 7.37, 7.40,
7.45, 7.46, 7.47, 7.49.
- Dec 5: Click here to view your marks
(by student number). Please let me know if there are any
discrepancies. Note that I have also calculated your term mark out of
60; make sure that it corresponds to your grades (especially for those
who did not write some of the tests).
- Nov 28: Test 4 with solutions has been posted below.
- Nov 25: Greg Herman will hold extra office hours over the
weekend: on Saturday, from 12:00 till 4:30 on Sunday, from 3:00 till
7:00.
- Nov 21: Test 4 is on Monday Nov 28, 11:30-12:20, in REF-102.
The test will comprise chapter 7; to prepare, do all the exercises and
problems in chapter 7, except for the starred problems and problem
7.39. You are responsible for all the material in chapter 7, except
for the proof of Theorem 7.37 which we are going to cover after the
test -- you are responsible for the statement of the theorem, however
(in other words, know that SAT and 3SAT are NP-complete, and we'll see
the proof after the test).
- Nov 14: Test 3 with solutions has been posted below.
- Nov 11: Click here for Test
3 comments by Tim Paterson (only marker).
- Nov 8: A reminder that Test 3 is tomorrow, in REF-102, and it
will comprise chapters 4 and 5.
- Nov 8: Here are some hints for doing problems in chapter 5.
- For question 5.25 use the language in 5.24: let B=J, and use the
reduction f(w)=0x if w=1x and f(w)=1x if w=0x, for some x.
- 5.33: to show that S complement is not Turing-recognizable, give
a reduction from the complement of A_TM: f(M,w)=N_(M,w), where N_(M,w)
is a Turing machine which on input x, first checks that x=(M,w), and
if no rejects, and if yes, it simulates M on w, and accepts if
M(w)=accept. Now show the correctness of this reduction.
- Oct 25: Note from Grzegorz concerning Test 2: If there are
any students which had used GRAMMARS (but NOT languages!) instead of
grammar starting symbols in solution to question 1 and had their marks
reduced FOR THAT REASON ONLY, please contact me and we will correct
the marking.
- Oct 17: Here are some clarifications for problems we did today
in the lecture:
- 3.12 We simulate an ordinary TM with a reset TM that has only
the RESET and Right head motions. When the ordinary TM moves right,
so does the reset TM. When the ordinary TM moves left, the reset TM
cannot, so it needs to accomplish the same effect differently; here is
one way to accomplish this: it marks the current square on the tape,
resets, and moves the contents of every square one square to the
right, but keeps the same square marked, so after this stage, the
symbol to the left is in the marked square. Then it resets again, and
scans the contents all the way to the right, until it finds the marked
square, at which point it performs on it the same operation that the
original TM would have done.
- 2.42 Assume Y is CF, let p be its pumping length, and consider
s=1^{p+1}#1^{p+2}#...#1^{5p}, where 1^{j} means 1 j-many times. Let
s=uvxyz, satisfying the three conditions of the lemma. Two cases: (1)
if v or y contains #, then uv^3xy^3z has two consecutive t's with the
same number of 1s, which is not in Y. (2) If both v,y contain only
1s, then since |vxy|<=p, we know that v,y are either in the same block
of 1s, or in two consecutive blocks of 1s. Now consider two subcases:
if v is in a block from 1^{p+1} to 1^{3p}, then pump v,y by 1. If v is
in the higher blocks, pump them both down to 0. In each case you get
a match with a higher (lower) block, and a contradiction.
- 2.6d) Here is a solution: S-->R#P#R|P#R|R#P|P corresponding the
the palindrome being in the middle, to the left or right, or by
itself. Now P-->aPa|bPb|a|b|epsilon|#|#R# corresponding to creating a
palindrome (first 5 rules), and the last two rules put 0 or more
strings in the middle of the palindrome. Finally, give a rule for
creating an arbitrary string from R, and you are done.
- Oct 17: New instructor office hours: Mondays, 11:30-12:20, in
ITB-214.
- Oct 15: Test 2 on Wednesday October 19, 11:30-12:20, in T28-001.
The test will comprise chapters 2 and 3.
- Oct 3: Test 1: click here
to read Tim's marking comments; click here for Grzegorz's comments.
- Sept 30: Test 1 with solutions has been posted below.
- Sept 29: The instructor's office hours will be on Mondays
10:30-11:20.
- Sept 28: If you were not on the sign-up sheet for Test 1, I
added you to my master class list by hand, but it is your
responsibility to check that you are properly registered in the
course.
- Sept 27: VERY IMPORTANT: The room for test 1
has changed! The new room is REF-102.
- Sept 21: Important: there has been a change of the tutorial
room; it is now ABB/136, effective Tuesday September 27th, still the
same time (10:30-11:20).
- Sept 21: Please note the dates for the tests:
- Wednesday September 28, 11:30-12:20, in REF-102
- Wednesday October 19, 11:30-12:20, in T28-001
- Wednesday November 9, 11:30-12:20, in REF-102
- Monday November 28, 11:30-12:20, in REF-102
Note that all tests will be written during the usual lecture time.
- Sept 19: The first test will take place on Wednesday Sept. 28,
during the usual lecture time (11:30-12:20). The room will be
announced shortly.
- Sept 19: The first tutorial will take place tomorrow (Tuesday
Sept. 20).
Tests and suggested exercises:
- Exercises and problems in chapter 7. (All the exercises and
problems in chapter 7, including the *'ed ones, except for 7.35, 7.37,
7.40, 7.45, 7.46, 7.47, 7.49.)
- All exercises and problems in chapter 5.
- Exercises and Problems in chapter 4 (including starred ones).
- Exercises and Problems in chapter 3 (including starred ones),
except 3.20 and 3.21.
- Exercises and Problems in chapter 2, except the starred
problems. I will do 2.21 (which is a starred problem) in class on
Friday Oct 7th.
- Do all the exercises and problems in chapter 1, except those
that are marked with a star (except 1.52, which is marked with a star,
but it contains an important result that you are responsible for).
- Test 1 with solutions
- Test 2 with solutions
- Test 3 with solutions
- Test 4 with solutions
- Final Exam