CS 5800 (Spring 2022)


Theory Foundations


[ Courses ] [ syllabus ] [ class list ] [ references ] [ projects ] [ assignments ]




Dr. Elise de Doncker
B-240 CEAS
Phone: (269) 276-3102 (Office), 276-3101 (Dept. office), 276-3122 (fax)
(but preferably contact me by e-mail:)
elise [dot] dedoncker [at] wmich [dot] edu

Office hours
Time after class on MW - please let me know if you plan on staying; other times by appointment

CS 3310

Catalog Description
The course gives an introduction to the theory of computation emphasizing automata, grammars and their applications in the specification of languages and computer systems, models of computation, and complexity. Analytic and problem solving abilities will be reinforced, and concepts covered in the course will be applied to real-world problems.


  • Required:
    • Languages and Machines, Thomas A. Sudkamp, 3rd edition, Addison Wesley 2006 (ISBN: 0-321-32221-5)
  • Recommended:
    • Introduction to Automata Theory, Languages and Computation, John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, 2nd edition, Addison Wesley 2001 (ISBN: 0-201-44124-1)
    • Automata, Computability, and Complexity: Theory and Applications, Elaine A. Rich, Pearson Prentice Hall 2008 (ISBN: 0-13-228806-0; ISBN: 978-0-13-228806-4)

There will be two tests and a final examination. Tentatively, the tests will carry 50% of the grade, the lowest of the two tests will be dropped.
Other graded work will include assignments and may further include a project and presentation. Problems with cheating or class attendance may lead to a failing grade.

The following scale will be used to determine your final grade on the basis of your final average:
    A: 92.0 - 100.0,  BA: 88.0 -  91.9,  B: 82.0 -  87.9,  CB: 78.0 -  81.9,  C: 72.0 -  77.9,  DC: 68.0 -  71.9,  D: 60.0 -  67.9,  E:  below  60.0.

Academic Integrity Policies
You are responsible for making yourself aware of and understanding the policies and procedures in the Undergraduate Catalog that pertain to Academic Integrity. These policies include cheating, fabrication, falsification and forgery, multiple submission, plagiarism, complicity and computer misuse. If there is reason to believe you have been involved in academic dishonesty, you will be referred to the Office of Student Judicial Affairs. You will be given the opportunity to review the charge(s). If you believe you are not responsible, you will have the opportunity for a hearing. You should consult with me if you are uncertain about an issue of academic honesty prior to the submission of an assignment or test.
Due to the current COVID-19 Pandemic, and consistent with the State of Michigan* requirements and the WMU Safe Return plan (https://wmich.edu/safereturn), safety requirements are in place to minimize exposure to the Western Michigan University community. These guidelines apply to all in-person or hybrid classes held either inside or outside a WMU building.
Facial coverings (masks), over both the nose and mouth, are required for all students while in class, no matter the size of the space. This includes outdoor class settings where social distancing is not possible (i.e., at least six feet of space between individuals). Following this recommendation can minimize the transmission of the virus, which is spread between people interacting in close proximity through speaking, coughing, or sneezing. During specified classes in which facial coverings (masks) would prevent required class elements, students may remove facial coverings (masks) with instructor permission, in accordance with the exceptions in the Facial Covering (mask) Policy** ("such as playing an instrument, acting, singing, etc.").
Facial coverings (masks) must remain in place throughout the class. Any student who removes the mandatory facial covering (mask) during class will be required to leave the classroom immediately.
Facial coverings (masks) are not a substitute for social distancing. Students shall observe current social distancing guidelines in all instructional spaces, both indoors and outdoors. Students should avoid congregating around instructional space entrances before and after class sessions. Students should exit the instructional space immediately after the end of class to help ensure social distancing and to allow for those attending the next scheduled class session to enter.
Students who are unable to wear a facial covering (mask) for medical reasons must contact Disability Services for Students (https://wmich.edu/disabilityservices) before they attend class.
These guidelines are in place to ensure the safety of all students, faculty, and staff during the pandemic. Noncompliance is a violation of the class requirements and the Student Code of Honor (https://wmich.edu/conduct/expectations-students).

Additional instructor's notes: The above policy on academic dishonesty includes cheating by submitting tests, programming assignments or projects where the work (even in part) has been downloaded from the internet; this also applies to text in assignments and project reports. Cooperation among students on submitted work is not allowed. If you are caught there will be consequences.

Useful links

[ Courses ] [ syllabus ] [ class list ] [ references ] [ projects ] [ assignments ]