Old Announcements

• 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 exercises.
• 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:
  • 4 assignments, 5% each
  • 2 tests, 20% each
  • final exam, 40%
  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.
• 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.