Fall 2021 CS235

Welcome to CS235, an introduction to the theory of computation

About CS235

  • This course offers an introduction to the theory of computation. Topics include languages, regular expressions, finite automata, grammars, pushdown automata, and Turing machines. The first part of the course covers the Chomsky hierarchy of languages and their associated computational models. The second part of the course focuses on decidability issues and unsolvable problems. The final part of the course investigates complexity theory.

Brian Tjaden

CS235 Fall 2021 schedule

Please check this page frequently, as it is subject to change.






Sep 6

Labor Day

Sep 7

Sep 8

Sep 10

Oct 5

Oct 6

Oct 7

Midterm Exam 1

Oct 8

Oct 11

Indigenous Peoples' Day

Oct 12

Fall Break

Oct 13

Oct 15

Oct 26

Oct 27

Oct 29

Nov 22

Midterm Exam 2

Nov 23

Nov 24


Nov 25


Nov 26


Dec 13

Where do we go from here?

Assignment 9 due

Dec 14

Dec 15

Reading Period

Dec 16

Final Exams

Dec 17

Final Exams

Dec 20

Final Exams

Dec 21

Final Exams

Dec 22

Final Exams

Dec 23

Dec 24

Course Information for CS235


Digital computers can do a great deal that is useful, but not everything that is useful. Computers can be taught to recognize lots of complicated languages, but not all languages. The goal of CS235 is to explore the power and limitations of the modern digital computer.

We will introduce several restricted models of computing machines: finite automata; pushdown automata; and Turing machines. Each model assumes an esstential role in computer science. For example, finite automata are used to design and implement digital logic circuits. Pushdown automata and the languages they recognize are central to the theory of programming languages. Program time and space complexity are analyzed using Turing machines. Taken together, these models form an elegant theory of languages and computation. We will focus on the language aspects of this theory through an exploration of the Chomsky hierarchy of languages: finite automata and regular languages; pushdown automata and context-free grammars; Turing machines and recursively enumerable languages.

After a brief introduction to the theory of computation, we begin by introducing the problem of representation of languages by finite specifications. Initially, we will study the simplest language recognition devices: finite automata. Next, we will investigate properties of languages accepted by these machines. Then we switch gears and study an alternative model of computation: context-free grammars. By adding a stack memory to our finite state machines, we prove the equivalence of these two notions of computation. We complete our hierarchy of languages and computation by studying Turing machines and exploring the limits of computer power. The course concludes by examining complexity theory.

Learning Goals

The aim of this course is to enable students to engage in a world shaped by computation, so that students can evaluate and distinguish problems that can and cannot be solved by computers, and students can understand and analyze the complexity of such problems.

Students who complete this course should be able to:


The textbook for the course is Introduction to the Theory of Computation, 3rd Edition by Michael Sipser, published by Cengage Learning.

Course Requirements

Late Policy

Assignments are due at 11pm on their due dates. It is beneficial to student learning for course work to be completed regularly throughout the semester. Since much of the material in the course builds off of previous content from earlier in the course, it is helpful to keep on schedule so that students have the necessary background to engage with the material as it is presented in class together with their classmates.

Sometimes, however, prioritizing completion of an assignment by the deadline may not be the right personal choice for you. To encourage you to learn from the assignments while also affording flexibility when it benefits your health and well-being, you may use either of the following mechanisms to submit late (non-exam) assignment work without penalty:

  1. Self-serve 48-hour late pass: You may delay any assignment deadline by 48 hours by submitting this late pass notification form before the original deadline. There is no need for any other communication in this case.
    • The form requires a brief summary of progress (e.g., "#1 done, #2 stuck, #3 started" or "not started") and whether you anticipate seekind support (drop-in hours/appointment) for the assignment.
    • If the 48-hour extended deadline falls during a break or weekend, it is automatically moved to the final day of that break or weekend.
  2. Custom extension: If you need to extend an assignment deadline more than 48 hours, of if you did not submit a late pass notification in time, you must email the instructor with an initial timeline and plan for when and how you will complete the assignment and report on progress.
    • We will adjust the plan together to make sure it is reasonable. The instructor may ask you to prioritize current work first. If you need custom extensions on multiple assignments, the instructor may ask you to check in with your class dean to make sure you are getting the support you need to manage your course load.
    • You are never required to discuss details of your personal circumstances with an instructor to receive an extension, altough we are happy to lend an ear. If you choose to share, please note that reporting duties prevent instuctors from holding strict confidentiality in all cases.

The above extension mechanisms are subject to the following limitations:

  1. Exams are not subject to extensions. Exam dates are fixed, as noted in the course calendar. Please arrange accommodations with the instructor at least 3 days ahead of exams. If an emergency prevents you from completing the exam as scheduled, we can schedule a make-up exam with the support of your class dean or health services. This sets a common standard for all students and ensures you are getting the support you need for your emergency.
  2. Feedback and grading for work submitted under an extensions will be completed eventually. This may take arbitrarily long, possibly past the end of classes and exams. The likelihood and likely magnitude of delay grow with the length of the extension.

Collaboration Policy

We believe that collaboration fosters a healthy and enjoyable educational environment. For this reason, we encourage you to talk with other students about the course material and to form study groups.

You are encouraged on any assignment to form a two-person "team" with a partner. The two team members must work closely together on the assignment and turn in a single assignment submission for the team. The grade received on such a submission will be given to both team members. When considering who to partner with for an assignment, you may find your own partner or you may use this shared Google document to indicate your interest in working with a partner.

Team efforts on assignments are subject to the following ground rules:

Unless otherwise instructed, teams are allowed to discuss problem sets with other teams and exchange ideas about how to solve them. However, there is a thin line between collaboration and plagiarizing the work of others. Therefore, I require that each (one-person or two-person) team must compose its own solutions to each assignment. In particular,

You must compose your own solution to each assignment. You may discuss strategies for approaching the problems with your classmates and may receive general advice from them, but you are required to write up all of your own solutions. Furthermore, you should never look at another student's solutions.
For example, it is OK to borrow ideas from the textbook, from materials discussed in class, and from other sources as long as you give proper credit. However it is unacceptable and constitutes a violation of the Honor Code (1) to write a solution together (with someone not part of your team) and turn in two copies of the same solution, (2) to copy a solution written by your classmates, (3) to read another student's or team's solution or (4) to view assignments, exams, and solutions from previous terms of CS235.

In keeping with the standards of the scientific community, you must give credit where credit is due. If you make use of an idea that was developed by (or jointly with) others, please reference them appropriately in your work. It is unacceptable for students to work together but not to acknowledge each other in their write-ups.

Grading Policy

For assignments, normally a subset of assigned problems will be graded. After assignments are submitted, sample solutions will be provided for all assigned problems.

Your final grade will be based on a weighted average of the following components:

At the end of the semester, we will compute a weighted average for each student and assign letter grades. In general, the mapping from numerical score to letter grades looks like this: >= 93.33 is an A, >= 90.00 is an A-, >= 86.67 is a B+, >= 83.33 is a B, >= 80.00 is a B-. >= 76.67 is a C+, >= 73.33 is a C, >= 70.00 is a C-, >= 60.00 is a D and < 60.00 is an F.

Depending on the overall performance of the class, we may adjust this mapping.

Google Group

There is a CS235 Google Group named CS-235-01-FA21. This group has several purposes. We will use it to make class announcements, such as corrections to assignments and clarifications of material discussed in class. We encourage you to post questions or comments that are of interest to students in the course. The instructor will read messages posted to the group on a regular basis and post answers to questions found there. If you know the answer to a classmate's question, feel free to post a reply yourself. The course group is also a good place to find people to join a study group. You should plan on reading group messages on a regular basis.

Anonymous Feedback Form

Here is a form for providing anonymous feedback to the instructor. You must be logged in to a Wellesley account to use the form, however neither your email address nor any other identifying information will be recorded.

Disabilities and Accommodations

If you have a disability or condition, either long-term or temporary, and need reasonable academic adjustments in this course, please contact Accessibility and Disability Resources to get a letter outlining your accommodation needs, and submit that letter to me. You should request accommodations as early as possible in the semester, or before the semester begins, since some situations can require significant time for review and accommodation design. If you need immediate accommodations, please arrange to meet with me as soon as possible. If you are unsure but suspect you may have an undocumented need for accommodations, you are encouraged to contact Accessibility and Disability Resources. They can provide assistance including screening and referral for assessments.

Accessibility and Disability Resources can be reached at accessibility@wellesley.edu, at 781-283-2434, by scheduling an appointment online at their website www.Wellesley.edu/adr , or by visiting their offices on the 3rd floor of Clapp Library, rooms 316 and 315.

Faculty Responsibilities on Disclosures of Discrimination, Harassment, and Sexual Misconduct

Pursuant to Wellesley College policy, all employees, including faculty, are considered responsible employees. That means that any disclosure of discrimination, harassment, or sexual misconduct to a faculty member will need to be shared with the College's Director of Non-Discrimination Initiatives / Title IX and ADA / Section 504 Coordinator (781-283-2451; titleix@wellesley.edu). Students who do not wish to have these issues disclosed to the College should speak with confidential resources who are the only offices at the College that do not have this same reporting obligation. On campus, confidential resources include Health Services (781-283-2810 available 24/7), the Stone Center Counseling Services (781-283-2839 available 24/7) and the Office of Religious and Spiritual Life (781-283-2685). You should assume that any person employed on campus outside of these three confidential offices has an obligation to share information with Wellesley College through the Office of Non-Discrimination Initiatives.