Comp Sci 2MJ3: Theory of Computation
- 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 BSB/104, and tutorial on T 8:30-9:20, in
- 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
Introduction to the Theory of Computation,
by Michael Sipser:
Book's web site
- Check this web page regularly for announcements.
- Previous versions of this course:
Note that this course was taught before as a Software Engineering
- Please Read:
McMaster Academic Integrity Statement.
- Nov 17: Test 4 will take place on Friday November 24 as
scheduled. The test will be on chapter 5, sections 1 and 2 (section 2
is just one short result, so I will present it on Monday). On
Tuesday (during the tutorial) and on Wednesday (during the lecture),
we are going to review for Test 4. During the last week of classes
will do section 5.3, which will be tested on the final exam. The
questions relevant for Test 4 are posted below.
- Nov 15: Test 3 with solutions has been posted below.
- Oct 27: Exercises for chapter 3 posted below.
- Oct 22: Since Greg gave two tutorials this week (in preparation
for Test 2), there will be no tutorial on Tuesday Oct 24. Test 2 with
solutions has been posted below.
- Oct 16: CFLs are not closed under interesection, but we'll
have to wait until chapter 5 to prove it.
- Oct 12: The problems for chapter 2 have been posted below.
Remember you must also do all the exercises, to prepare for the test
on Friday Oct 20.
- Oct 2: Test 1 with solutions has been posted below.
- Sept 29: Test 1 is rescheduled for Monday October 2, at
11:30-12:20, in BSB/104 (the usual classroom, the usual Monday lecture
- Sept 25: The first test is coming up this
Friday (Sept 29). Make sure you know how to do the
exercises listed below.
- Sept 14: Test dates:
The tests will be written in the usual lecture room (BSB/104). Also
note that the tests are every 3 weeks, except the last two tests are 2
weeks apart (due to the test ban).
- Test 1: Monday Oct 2 (originally scheduled for Friday Sept 29)
- Test 2: Friday Oct 20
- Test 3: Friday Nov 10
- Test 4: Friday Nov 24
- The first two lectures, Friday September 8, and Monday September
11, will be taught by Greg Herman.
Each chapter in Sipser has a set of exercises (to test basic
understanding of the material), and problems (to develop problem
solving skills in the area). You must do all the exercises, but only
the problems listed below. Remember that the problems on the tests
will be based on the problems in Sipser.
| Test 1 || Chp 0: 0.12,0.13
|| Chp 1: 1.31--1.39
|| Chp 1: 1.51, 52 (Myhill-Nerode Thm) 1.53, 1.54
| Test 2 || Chp 2: 2.18,19,21-24,26,30,31,35
| Test 3 || Chp 3: 3.9-20
|| Chp 4: 4.9-28
| Test 4 || Chp 5: 5.1-3,8,5.9-15,5.17-20.