Formal Languages and Automata Theory

198:452 and 198:508

Spring, 2021

Professor Eric Allender

Phone: (848) 445-7296


Office: Hill 442
(In Spring 2021, Hill 442 will not be used much. To meet with me, contact me via e-mail to set up a meeting via WebEx.) Click here for current Office Hours.

Lectures will be presented as scheduled: Tuesdays and Fridays, noon - 1:20.
They will also be recorded for later use. Videos of the lectures are available here.
Enrolled students will receive announcements via Sakai, regarding how to connect to WebEx for lectures.

Teaching Assistant: Guido Tagliavini

Office hours for TA: Fridays 9-10:30 AM
URL for TA's office hours:

Text: Michael Sipser, Introduction to the Theory of Computation. Please also take note of the list of errata for the textbook. Note that there are different editions of this textbook; if you purchase the "foreign edition" the exercise numbers are likely to be different.

Click here to find out about what was covered in class, and what material you should read next.

Click here to find out about homework.
(Also, here are some helpful Guidelines from last year's TA, which are still relevant.)

Click here to find recorded videos of the lectures this semester.
Other Resources:You may want to check out this on-line Theory of Computation Course.
Prerequisites:CS 206 and 344, or familiarity with induction, dynamic programming, and basic algorithms.

There will be frequent homework, along with 1-2 take-home midterm exams.
There will also be a take-home final exam, which will account for roughly one-fourth of your grade.

No collaboration or discussion of questions on the midterms or on the final exam is allowed (other than discussion with me). In contrast, I have no objection to your discussing the homework problems among yourselves (as well as with me). However, this discussion should be limited to an exchange of ideas concerning what approaches do and do not work. Under no circumstances should you show your work to any other student, or in any other way provide detailed information concerning your solutions.

Please be aware of our Departmental Academic Integrity Policy.

Students are expected to maintain the highest level of academic integrity. You should be familiar with the university policy on academic integrity. Violations will be reported and enforced according to this policy. Here is additional information about the enforcement policy, and other resources available to you.

Use of external website resources such as or others to obtain solutions to homework assignments, quizzes, or exams is cheating and a violation of the University Academic Integrity policy. Cheating in the course may result in grade penalties, disciplinary sanctions or educational sanctions. Posting homework assignments, or exams, to external sites without the instructor's permission may be a violation of copyright and may constitute the facilitation of dishonesty, which may result in the same penalties as plain cheating.

Students will need to acknowledge the Rutgers Honor Pledge on every major exam assignment as follows:
On my honor, I have neither received nor given any unauthorized assistance on this examination/assignment.

Please visit the Rutgers Student Tech Guide page for resources available to all students. If you do not have the appropriate technology for financial reasons, please email Dean of Students for assistance. If you are facing other financial hardships, please visit the Office of Financial Aid.

Learning remotely presents new challenges. For assistance with learning how to address these challenges, please consult the resources available here. The faculty and staff at Rutgers are committed to your success. Students who are successful tend to seek out resources that enable them to excel academically, maintain their health and wellness, prepare for future careers, navigate college life and finances, and connect with the RU community. Resources that can help you succeed and connect with the Rutgers community can be found at and nearly all services and resources that are typically provided in-person are now available remotely.