Web page contents:

General Information

Teaching Assistants' office hours:

• No longer being held.

Take a look at the departmental guidelines on academic honesty.

Marking Scheme

Announcements

Upcoming Office Hours:

• Apr 5, 3:00-4:00
• Apr 8, 3:00-4:00
• Apr 11, 2:00-3:00
• Apr 13, 2:00-3:00
• Apr 15, 3:00-5:00
• Apr 18, 3:30-4:30

Regular Announcements:

• Apr 6: Solutions for assignment 3 have now been posted at the bottom of this page.
• Apr 4: I will be having office hours between now and the exam. The times will be posted here.
• Apr 4: The marking scheme for assignment 2 is posted at the bottom of this page. Solutions for assignment 3 will be posted soon. You can check your marks using courseInfo.
• Mar 30: Clarification of Q1 on Assignment 3. "either x=y, y=z or x=z" means at least one of those three statements is true. (It's an inclusive or of three statements.)
• Mar 30: I will be having office hours between now and exams, but probably not at the usual times. Times will be posted here. (They will depend to some extent on whether there is a TTC strike.)
• Mar 30: You can bring your 3rd problem set to my office on Monday. If I'm not there, you can slide it under the door.
• Mar 17: Test 2 will cover everything up to the end of the March 14 lecture. This includes all of the material on CFGs and PDAs (Section II of the readings, below). The focus of the test will be on material covered after February 2, but I could still ask something related to the first part of the course.
• Mar 14: Today's TA office hour is cancelled due a sick leave.
• Mar 13: It may be necessary to reschedule tomorrow's TA office hour. Watch this space for announcements.
• Mar 3: Come to the York programming contest on March 11, 2-4 p.m. in the demo lab.
• Mar 3: Course evaluations will be done in class on March 23.
• Feb 22: If, during the term, you want to check my record of your marks, you can use the command "courseInfo 2001" when you are logged into your cs account.
• Feb 18: The TA office hours on Fridays will be a bit later than before: from now on, they will be from 16:00 to 17:00.
• Feb 14: There will be no TA office hours during reading week. Also my office hour on Feb 16 is cancelled.
• Feb 8: Come to the York Programming Contest on Friday, February 11! All students are eligible. The contest will be in CSEB1004 from 14:00 to 16:00, with refreshments afterwards. See this link for further details.
• Feb 7: My solution to assignment 1, question 1 should mention that the strings in the language do not contain bb as a substring. In my solutions to question 5(c) and 5(d), I accidentally used the letter x for two different things. Replace the three occurrences of the letter x in 5(c) and the first three occurrences in 5(d) by the letter m.
• Feb 4: The first test will cover the material up to the end of the Feb 2 lecture. In the textbook, this corresponds to all of the readings listed under "Regular Languages" below, except Section 4.3
• Jan 29: Note that TA's office hours will begin next week (see above).
• Jan 27: A student asked whether j-k must be positive for Q5 of assignment 1. The answer is no.
• Jan 24: Come to the computer science student-faculty forum in lecture hall B of the Computer Science Building on Fri, Feb 4 at 4:30p.m. Key topics include study abroad opportunities, NSERC summer research awards, Women in CSE, ACM programming contest, internship programme, curriculum, CRA Award. You can also contribute thoughts or concerns about the department.
• Jan 18: On assignment 1, the alphabet for Q3 is {a}, and the alphabet for Q5 is {a,b}.
• Jan 17: If you're interested in working at York on a research project next summer, see this link. This is a great opportunity.
• Jan 15: Assignment 1 has been posted below.

Important Dates

First class	January 3
Assignment 1 due	February 7
Test 1	February 9
Reading Week	February 14-18
Last date to drop course without receiving a grade	March 4
Assignment 2 due	March 14
Test 2	March 21
Last class	March 30

Resources

Textbook

• John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation, Second Edition. Addison-Wesley, 2001. Solutions to selected exercises and errata can be found on the textbook's web site.

Other References

• Ding-Zhu Du and Ker-I Ko. Problem Solving in Automata, Languages, and Complexity. Wiley, 2001.
• John C. Martin. Introduction to Languages and the Theory of Computation. McGraw-Hill, 2003.
• Michael Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
• Daniel Solow. How to Read and Do Proofs: An Introduction to Mathematical Thought Processes. Wiley, 2002.
• Andrew Wohlgemuth. Introduction to Proof in Abstract Mathematics. Saunders College Publishing, 1990.

Web Links

• The web page for this course the last time I taught it is here.
• Jeff Edmonds has some online notes that he uses when he teaches this course.
• links to web pages on theoretical computer science

Reading

Section I: Regular Languages (about 5 weeks)

Supplemental reading: Jeff Edmonds's notes on proving languages non-regular.

Section II: Context-Free Languages (about 3 weeks)

Section III: Turing Machines (about 3 weeks)

Course Handouts

• Assignment 1
• Assignment 2
• Assignment 2 marking scheme
• Assignment 3
• Assignment 3 solutions

Updated April 9, 2005