Back to main page
- Nov 16: See below for the first part of the notes on
computability theory. You are responsible for the material in these
notes for Test 2.
- Nov 15: We did not cover much of chapter 6; you are responsible
for sections 6.1.1 and 6.1.2 only.
- Nov 14: Test 2 is going to take place on Monday (Nov 19) in
class. The test is 50min, and it has 4 questions. The first two deal
with CFGs and PDAs, and the last two with Turing Machines. To prepare
for the test, review the notes from class, especially the notes
dealing with TMs, as we did not follow the book for this part of the
course. Also, make sure that you know how to do the suggested
- Nov 14: Solutions to Assignment 3 have been posted below.
- Nov 12: Today's class (Monday, Nov 12) was canceled. You can
hand in assignment 3 in class on Wednesday, or you can leave it in
my mailbox, or slide it under my door.
- Nov 9: Click here for a hint on how to
do question 5.1.3 on Assignment 3. Also note that in question 5.2.1
you do not have to give the parse tree for the grammar, as we have not
mentioned parse trees for grammars in the lectures. You have to give
parse trees only for the three strings.
- Nov 5: Suggested exercises: 5.4.1--3. Test 2 is going to be
based again on the suggested exercises (since Test 1). Make sure that
you do these exercises to be prepared.
- Oct 31: Suggested exercises: 5.1.1--3.
- Oct 31: Below are the dates for Test 2 and Assignments 3 and 4.
There was a request to move assignment 3 to Nov 12. Test 2 will be on
Nov 19, to make it cover a little less material.
- Oct 31: Test and Assignments dates:
- Assignment 3: Nov 12 (Monday)
- Test 2: Nov 19 (Monday)
- Assignment 4: Nov 30 (Friday)
- Oct 26: Solutions to Assignment 2 are posted below.
- Oct 26: Suggested exercises: 4.4.1 and 4.4.2
- Oct 26: Test 1 was returned in class today. The TAs marked the
test (the TAs will mark all the term work: assignments 1,2,3,4 and
tests 1,2, I will mark the final exam). If you have marking concerns,
you should talk with the TAs during their office hours (Mondays
12:30--2:30 in ITC222). If the concern is not resolved with the TAs,
you can then talk to me.
- Oct 22: For questions 4.3.3 and 4.3.4 on Assignment 2, an informal
english description of the algorith is all that is needed. For example,
we showed how to determine if a reg language is empty by using the
reachability algorithm on its DFA.
- Oct 22: The class on Wednesday Oct 26 has been cancelled.
- Oct 19: Test 1 solutions have been posted below.
- Oct 15: New TA office hours: Mondays 12:30--2:30 in ITC222.
- Oct 11: Test 1 will comprise chapters 2 and 3, and section 4.1,
in the book. You should prepare by doing all the suggested exercises.
The test will take place in class, and it will last 50min. There will
be three problems on the test, chosen from the suggested exercises.
- Oct 10: Test 1 is next week (Wed Oct 17). Make sure that you do
all the suggested exercises from the book to prepare.
- Oct 10: Assignment 2: Due in class, on Friday Oct 26: problem
4.1.1 and one more problem to be assigned later.
- Oct 10: Suggested exercises: 4.1.1--2.
- Oct 10: We will choose new office hours on Friday Oct 12, in
class, but today you should go to the usual office hours (12:30pm
until 2:30pm, in room ITC222).
- Oct 5: Suggested exercises: 3.2.4--7 and 3.4.1--2.
- Sept 28: I updated the solutions to assignment 1 (the solution to
question 2.2.5(a) is now fixed).
- Sept 26: Test 1 will take place on Wed Oct 17.
- Sept 26: Suggested exercises: 3.1.1--5
- Sept 26: Click here for the solutions
to Assignment 1.
- Sept 21: Suggested exercises: 2.5.1--3
- Sept 19: There was a question regarding the action of the delta
(transition) function on epsilon. In fact, we DO have to specify what
delta does to epsilon in epsilon-NFAs. Whenever, in a diagram, it is
not shown what happens to epsilon, we assume the empty set. That is,
unless it is specified otherwise, delta(q,epsilon)=empty.
- Sept 17: Suggested exercises (not to hand in) 2.3.1--7.
- Sept 17: After today's vote in class, we established that the
marking scheme for the course is as follows:
The assignments will be exercises from the book, the first set
(exercises 2.2.5 and 2.2.7) is due on Wednesday, Sept 26.
- 4 assignments, 5% each
- 2 tests, 20% each
- final exam, 40%
- Sept 14: The TAs, Feng Liu and Yuwen Yang, will hold office hours
every week on Wednesdays, from 12:30pm until 2:30pm, in room ITC222.
- Sept 12: Suggested exercises: pp 53 and 54, 2.2.1-11. In
particular, hand in exercises 2.2.5 and 2.2.7 (in class, Sept 26).
The problems on the tests (and on the final) will be in the style of
the exercises in the book, some of them actually taken from the book,
so it is important that you do them. The exercises that you hand in
will be graded, but they will not count towards the course, so in that
sense they are optional.