Formal Languages and Automata Theory

198:452 and 198:508

Fall, 2022

Professor Eric Allender

Phone: (848) 445-7296


Office: Hill 442
Click here for current Office Hours.

Lectures will be presented live and in-person, Tuesdays and Thursdays, 3:50-5:10.
(Dr. Allender is fully-vaccinated.)
Videos of lectures from Spring 2021 and part of Spring 2020 are available here.

Teaching Assistant: TBA
Email: TBA

Office hours for TA: TBA

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" or "international 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 a previous year's TA, which are still relevant.)

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 midterm exams.
There will also be a take-home final exam.

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.

Face Coverings
In order to protect the health and well-being of all members of the University community, masks must be worn by all persons on campus when in the presence of others (within six feet) and in buildings in non-private enclosed settings (e.g., common workspaces, workstations, meeting rooms, classrooms, etc.). Masks must be worn during class meetings; any student not wearing a mask will be asked to leave. (I personally do not enjoy wearing a mask, and although I was delighted to learn that I would be teaching face-to-face again this semester, I did not anticipate that I would be wearing a mask when teaching. Nonetheless, I will be wearing a mask. You will be wearing one, too.) If Rutgers changes its policy regarding masks, then this policy will be updated as well.

Masks should conform to CDC guidelines and should completely cover the nose and mouth.

Each day before you arrive on campus or leave your residence hall, you must complete the brief survey on the My Campus Pass symptom checker self-screening app.

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.

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
Rutgers CS Diversity and Inclusion Statement
Rutgers Computer Science Department is committed to creating a consciously anti-racist, inclusive community that welcomes diversity in various dimensions (e.g., race, national origin, gender, sexuality, disability status, class, or religious beliefs). We will not tolerate micro-aggressions and discrimination that creates a hostile atmosphere in the class and/or threatens the well-being of our students. We will continuously strive to create a safe learning environment that allows for the open exchange of ideas while also ensuring equitable opportunities and respect for all of us. Our goal is to maintain an environment where students, staff, and faculty can contribute without the fear of ridicule or intolerant or offensive language. If you witness or experience racism, discrimination micro-aggressions, or other offensive behavior, you are encouraged to bring it to the attention to the undergraduate program director, the graduate program director, or the department chair. You can also report it to the Bias Incident Reporting System