Automata Theory and Formal Grammars
Syllabus

Version of March 20th, 2019

Course meeting details

Our class meets every Tuesday and Thursday from April 2nd to June 6th, 1:30pm to 3pm. At the moment the class is listed as meeting in room 224 of the CDM building (243 S. Wabash) but please check that shortly before the first class as room assignments sometimes change at the last minute.

Course description

From the course catalog: "An introduction to the most important abstract models of computation and their applications: finite state machines and pushdown automata. Explores the relationship between regular expressions and formal grammars and automata. Prerequisites: CSC 301 and MAT 141

Course web site

Except for the textbook, all course materials will be available through DePaul's D2L web site.

Textbook

There is one required textbook and its title is Automata, Computability and Complexity, by Elaine Rich (Pearson, 2007); ISBN 978-0132288064. An on-line version is also available through Safari and that can be accessed through DePaul's library site.

Course learning outcomes

Upon successful completion of this course, a student will be able to:

Assignments and grading

There will be weekly assignments, for the nost part asking you for written answers but there will also be some programming exercises. These will total 500 points. The final exam will be worth 100 points. There will not be a midterm.

Letter grades will be assigned as follows:

Letter Percentage range
A 95-100
A- 90 - <95
B+ 87 - <90
B 83 - <87
B- 80 - <83
C+ 77 - <80
C 73 - <77
C- 70 - <73
D+ 65 - <70
D 60 - <65
F <60

Schedule of topics

Week (date) Topic Textbook Sections
1 (4/2, 4/4) Mathematical foundations Chapters 1 and 2
2 (4/9, 4/11) Computation and languages Chapters 3 and 4
3 (4/16, 4/18) Regular languages and FSMs Chapters 5 and 6
4 (4/23, 4/25) Regular languages and FSMs Chapters 7 and 8
5 (4/30, 5/2) Regular languages and FSMs Chapter 9
6 (5/7, 5/9) Context-free languages and PDAs Chapters 10 and 11
7 (5/14, 5/16) Context-free languages and PDAs Chapters 12 and 13
8 (5/21, 5/23) Context-free languages and PDAs Chapters 14 and 15
9 (5/28, 5/30) Parsing Chapter 16
10 (6/4, 6/6) Applications and course review Review chapters

Dates and deadlines

The dates specific to our class are in bold.

Participation policy

For students in the in-class section, attending every class is required. Students in the distance learning section must send me an email each week when they've finished viewing the class recording.

Academic Integrity Policy

This course will be subject to the academic integrity policy passed by our faculty. More information can be found at http://academicintegrity.depaul.edu/.  I strongly recommend that you read this!  It explains both your rights and your responsibilities as a student on matters of academic integrity.

Communication

All communication will be done in one of three ways:

You may call my office phone and leave a voice message but I'm more likely to respond to it with an email than with a return call.

When you send me email, two requirements:

  1. Please have the subject line begin with CSC 403:
  2. Make sure your full name appears somewhere in the message.

Office location and hours

My office is room 747 in the CDM building, 243 S. Wabash. My office hours can be found through BlueStar, which can be accessed through your Campus Connect account. My phone number is 312-362-8334 (dial 2-8334 from the 7th floor lobby phone). If you call and do not leave a voicemail, I will not try to contact you. If you want a response, you must leave a message!

Plagiarism

The university and school policy on plagiarism can be summarized as follows: Students in this course should be aware of the strong sanctions that can be imposed against someone guilty of plagiarism. If proven, a charge of plagiarism could result in an automatic F in the course and possible expulsion. The strongest of sanctions will be imposed on anyone who submits as his/her own work any assignment which has been prepared by someone else. If you have any questions or doubts about what plagiarism entails or how to properly acknowledge source materials consult the instructor.

Incomplete

An incomplete grade is given only for an exceptional reason such as, for example, a death in the family or a serious illness.  Any such reason must be documented. Any incomplete request must be made at least two weeks before the final and approved by the Dean of the College of Computing and Digital Media. Any consequences resulting from a poor grade for the course will not be considered as valid reasons for such a request.

Resources for Students with Disabilities

Students who feel they may need an accommodation based on the impact of a disability should contact the instructor privately to discuss their specific needs. All discussions will remain confidential.

To ensure that you receive the most appropriate accommodation based on your needs, contact the instructor as early as possible in the quarter (preferably within the first week of class) and make sure that you have contacted either the PLuS Program, for Learning Disabilities and/or AD/HD, or the Office for Students with Disabilities, for all other disabilities, at:

Student Center, LPC, Suite #370
Phone number: (773) 325-1677
Fax: (773) 325-3720
TTY: (773) 325-7296