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.

Graders: Sharath Chandra Punna and Girish Ganesan
Email: and

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
Rutgers University is no longer requiring face coverings. Of course, you are welcome to wear a mask if you prefer. I have been lecturing un-masked since the start of October, 2022.

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.

In the last few years, we have all been going through a lot, individually and together. It is important to acknowledge that events and circumstances outside of the classroom can impact our ability to be present and engaged at any given moment. At Rutgers, we are focused on the whole student. If, at any point, you experience anything impacting your performance or ability to participate in this class, please reach out to me. Please also see the academic, health, and mental wellness resources on the syllabus as well as others searchable at for further support.

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