Theory of Automata

Instructor:
Prof. Brett Stevens,
Herzberg Physics, Office #4374
Tel: (613) 520 2600 (Ext. 2125)
Email:stevens@math.carleton.ca
http://mathstat.math.carleton.ca/~brett/

IMPORTANT ANNOUNCEMENTS

General Information

Textbook:
Finite Automata by Mark V. Lawson. I have ordered this book at Haven Books . Additionally I four books will be on reserve at the library for this course. They will be

• Finite Automata by Mark V. Lawson
• Formal Languages and Their relation to Automata by Hopcroft and Ullman.
• Introduction to the Theory of Computation by Sipser.
• An introduction to formal languages and automata by Linz.

Prerequisites:
MATH3805, MATH3106, MATH3158, MATH3100, equivalents, or permission.
Students who have not passed the prerequisite course may be automatically de-registered during the term.

Classes:
Tuesday 8:35-9:55, Thursday 8:35-9:55.
Room: HP4369.

Office hours: Monday 12:00-13:30 and Tuesday 10:00-11:30 or by appointment.

Classes begin: Thursday 8 Sep. 2011. Classes end: Thursday 1 Dec. 2011.

Term mark: There will be two assignments and a midterm. The tentative schedule of is:

Item	Hand-out Date	Due Date	Worth
Homework 1	Sep. 29	Oct. 27	20%
Midterm		Oct. 27	25%
Homework 2	Nov. 1	Dec. 1	20%

Evaluation:
20% Homework 1
25% Midterm Test
20% Homework 2
35% Exam
You must pass the term work in order to pass the course. If you have a passing term mark and you do better on the final exam then I will count your final exam for 100% of the course. I do not accept doctor's notes for late or missed work because I cannot verify the authenticity. Students wishing to see their examination papers must make an appointment within 3 weeks of the examination. This is an opportunity to get educational feedback and not an opportunity to argue about the marking.

Plagiarism and Cheating:
Plagiarism is defined in the undergraduate calendar as an instructional offense that occurs when a student uses or passes off "as one's own idea or product, work of another without expressly giving credit". This includes plagiarism involving material lifted from the Internet. Plagiarism is a serious offense. The penalties for students who have been found to have plagiarized are a failed grade at the least sever and suspension, expulsion or notation on transcripts for serious or repeated cases. Plagiarism is just one form of Cheating. All forms of cheating are taken very seriously and will be dealt with swiftly and severely.

Withdrawal: The last day for withdrawal from the course is 5 Dec. 2011. Withdrawals before 30 Sep. 2011 get 100% refund, there is NO refund after this date.

Academic Accommodation You may need special arrangements to meet your academic obligations during the term. For an accommodation request the processes are as follows:

• Pregnancy obligation: write to me with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details see the Student Guide
• Religious obligation: write to me with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details see the Student Guide
• Students with disabilities requiring academic accommodations in this course must register with the Paul Menton Centre for Students with Disabilities (PMC) for a formal evaluation of disability-related needs. Documented disabilities could include but are not limited to mobility/physical impairments, specific Learning Disabilities (LD), psychiatric/psychological disabilities, sensory disabilities, Attention Deficit Hyperactivity Disorder (ADHD), and chronic medical conditions. Registered PMC students are required to contact the PMC, 613-520-6608, every term to ensure that I receive your Letter of Accommodation, no later than two weeks before the first assignment is due or the first in-class test/midterm requiring accommodations. If you only require accommodations for your formally scheduled exam(s) in this course, please submit your request for accommodations to PMC by the deadlines published on the PMC website.

List of Topics Covered: regular languages, finite state automata, non-determinism, Kleene's Theorem, Pumping Lemma, Minimization and algorithmic problems. Additional topics that might be covered include: grammars, push down automata, context-free languages, transducers, the algebraic theory of automata, semigroups, Turing machines, Schutzenberger's theorem.

These topics are subject to change