Comp Sci 2MJ3: Theory of Computation
Fall 2010
- Instructor: Michael Soltys, email:
my last name at mcmaster.ca
- Course Outline (updated
on Sept 9)
- Time: lectures on Mo, We, Th, 10:30-11:20, in
BSB/136, and tutorials:
- T01: We, 13:30-14:20, T13/105 (revised Sept 13)
- T02: We, 14:30-15:20, BSB/B155 (revised Sept 13)
- 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.
- Textbook:
Introduction to the Theory of Computation, 2nd Edition, by Michael
Sipser:
Book's web
page
- Check this web page regularly for announcements.
- Previous versions of this course:
2006,
2009.
- Please Read:
McMaster Academic Integrity Statement.
Announcements:
- Dec 20: The tests are still available for pick up - they are in
a box in front of my office. They will be there until Wednesday.
- Dec 14, 2:45pm: The tests are in a box in front of my office.
- Dec 14: You can pick up test 6 today between, approximately,
the hours of 11am and 3pm, from my office (ITB-214).
- Dec 3: Notes on PCP.
- Nov 30: Please be advised that all the December examinations
that were originally scheduled in IWC2 (Smith Gymnasium) and IWC3
(East Auxiliary Gymnasium) will be moved to DBAC (David Braley
Athletic Centre) Sports Hall.
- Nov 18: The problems for chapters 4 and 5 have been posted
below. The last test, test #6, will be based on these problems.
The solutions to test #5 have been posted below.
- Nov 4: The latest batch of problems/exercises, for chapter 3,
has been posted below.
- Oct 22: The exercises for context-free languages have been
posted below. Remember that doing these exercises is essential for
doing well on the tests. Try them, discuss them with each other, and
ask the TA (or the instructor) to help you with the ones where you
have difficulties. Make good use of the TA office hours.
- Oct 20: The solutions to test 3 have been posted below.
- Oct 8: A new batch of problems, related to the pumping
lemma has been posted below.
- Oct 4: Test 2 with solutions posted below.
- Sept 28: In class on Monday Sept 27 we saw an example of a
translation of an NFA into a DFA. We took the NFA for the language
L_2, the 4-state NFA we already saw before, and translated it into the
corresponding DFA using the subset construction.
Click here
(updated Sept 29) for a scan of the procedure.
- Sept 27: A new set of suggested exercises has been posted below
(as preparation for test 2 on Monday Oct 4).
- Sept 22: Office hours start today; the solutions to test 1 have
been posted below.
- Sept 14: The first batch of problems have been posted below.
- Sept 13: The tutorials will start on Wednesday Sept 22; see
above for the revised tutorial hours.
- Sept 13: The instructor's office hours are Wednesdays
13:00-15:00.
Problems and tests:
The following are review problems from Sipser; it is important that
you do them in preparation for the test (they are not to be handed
in).
- Chapter 0: 0.1-0.9; 0.12-0.14
- Chapter 1: 1.1-1.14,1.16; 1.31-1.37
- Chapter 1: 1.15,1.17-23,1.28; 1.38-42 (posted Sept 27)
- Chapter 1: 1.46,48,51,52,54 (posted on Oct 8)
- Chapter 2: 2.1-35, except the starred one (posted Oct 22)
- Chapter 3: 3.1-16 and 3.18 (posted Nov 4)
- Chapter 4: 4.2,3,4; 4.9-19 (posted Nov 18)
- Chapter 5: 5.1,2; 5.4-7; 5.9-18 (posted Nov 18)
Given that we have 6 tests, and that October 11th is Thanksgiving, and
that tests cannot be scheduled starting November 30th, all six tests
will be given on Mondays, every two weeks, starting Monday September
20. The tests will be written in class, in the usual classroom--no
aids are allowed, and the duration will be 50 minutes.
