COURSE DESCRIPTION

This course covers a number of basic concepts in the theory of computation. These concepts are fundamental to many areas of computer science, e.g., programming languages, compiler construction, natural language and speech processing as well as theory of concurrency. We study regular languages, context-free languages and recursively enumerable languages. We also study abstract machines that accept these languages (finite automata, pushdown automata and Turing machines), as well as grammars that generate them. We also study the basics of computability theory, i.e. investigate the power and limitations of what we call ``computation''.

PREREQUISITES:

Mathematics 223b, or (registration in the 3rd or 4th year of an honors program that combines Computer Science and other mathematical science), or (SE 251a/b and registration in the 3rd year of the BESc program in Software Engineering). Unless you have either the requisites for this course or written special permission from your Dean to enroll in it, you will be removed from this course and it will be deleted from your record. This decision may not be appealed. You will receive no adjustment to your fees in the event that you are dropped from a course for failing to have the necessary prerequisites.

INSTRUCTOR

Lila Kari
385 Middlesex College
Office hours: Tuesdays 1:30pm - 3:20 pm, MC 385.
WWW page: http://www.csd.uwo.ca/~ lila

CLASS SCHEDULE

Tuesdays 10:30am-11:30am and Thursdays 9:30am -11:30am, 3M Bldg., room 3250.

TEXTBOOK, LECTURE NOTES

Required textbook: Automata Theory, Languages, and Computation by J.E.Hopcroft, R.Motwani and J.D.Ullman, 3rd edition, Addison Wesley, 2007.

Lecture notes will be available on the course website.

JFLAP (Java Formal Languages and Automata Package), an interactive visualization and teaching tool for formal languages, by Susan Rodger et al, available for free at www.jflap.org, will be used.

COURSE WEBSITE

The course website below will be used for posting announcements, assignments and lecture notes. Students are responsible for checking the website on a regular basis.

URL: http://www.csd.uwo.ca/~lila/331.html

TOPICS

• Basic concepts of (formal) words and languages,
• Finite automata and regular expressions,
• Pushdown automata and context-free grammars,
• Turing machines and computability.

• Each of the four assignments weights 10 % of the course grade.
• The in-class midterm test weights 25 % of the course grade
• The final exam weights 35 % of the course grade.
• If for any reason this schedule cannot be achieved, all marks above will be pro-rated.
• Assignments, tests and exams will be graded according to their correctness, precision, and elegance. Marks will be deducted for poor grammar, spelling errors, etc.
• In order to receive a grade higher than 45% in the course, the weighted average on the Midterm Test and the Final Exam must be at least 50%.

Sept.26	Tue.	Assignment 1 is due.	Nov. 14	Tue.	Assignment 3 is due
Oct.17	Tue.	Assignment 2 is due.	Dec. 05	Tue.	Assignment 4 is due
Oct.26	Thu.	In-class Midterm test.	TBA		Final exam

GENERAL COURSE CONDUCT

• Assignment Conduct -- Students are expected to complete assignments independently, unless otherwise indicated. All assignments are to be handed into the Computer Science 331 assignment locker. All assignments are due by 10pm of the due date. Late assignments will be accepted up to five days after the due date, with week-ends (Saturday and Sunday) counting as a single day. The late assignment policy is: marks will be deducted from assignments submitted after the due date, where is the number of days late.

  If there is a compelling reason why you are unable to finish an assignment by the deadline, please speak to the instructor before the assignment is due.

  Assignment extensions will be granted only by the course instructor. If you have serious medical or compassionate grounds for an extension, you should take supporting documentation to the office of the Dean of your faculty, who will contact the instructor.

• If for any reason the assignment schedules given above cannot be adhered to, the assignment marks will be pro-rated.

• There will be no makeup Midterm Test, except for students requesting a Special Midterm Test for religious reasons. These students must have notified the course instructor and filed documentation with their Dean's office at least 2 weeks prior to the Term Test.

  If you miss the Midterm Test for any other reason, and present valid documentation to the Dean's office, your Final Exam mark will be reweighted to include the weight of the Midterm Test. You must notify the course instructor within a week of the missed Term Test, and documentation must be received by your Dean's office within 2 weeks of the missed test.

EMAIL CONTACT

We will occasionally need to send email messages to the whole class, or to students individually. Email will be sent to your GAUL email address. You must make sure that you read your email on GAUL on a frequent and regular basis, or have it forwarded to an alternative email address if you prefer to read it there.

However, you should note that email at ITS (your UWO account) and other email providers such as hotmail.com or yahoo.com may have quotas or limits on the amount of space they can use. If you let your email accumulate there, your mailbox may fill up and you may lose important email from your instructors. Losing email that you have forwarded to an alternative email address is not an excuse for not knowing about the information that was sent.

ETHICAL CONDUCT

All assignments in this course are individual assignments. For the individual assignments in this course, you may discuss approaches to problems with others; however, the actual details of the work must be an individual effort. Copying solutions from other students or from other sources, or allowing your own solutions to be copied is a scholastic offence. The standard departmental penalty for such an offence is (for the student's first offence) a negative mark equal to the weight of the assignment. Cheating on exams, e.g. copying answers of another students or communicating in any way with another student will result in failure in the course. You are responsible for reading and respecting the Computer Science Department's policy on Scholastic Offences and Rules of Ethical Conduct.