Fall 2026 CS235

Overview

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. What are the problems we can solve and what are the ones we cannot? 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. We will practice known proof techniques and learn new ones, practice creating and presenting arguments in many forms (formal writing, drawings, presentations, working in groups), practice giving feedback, and sitting with the discomfort of learning very complex concepts. Throughout it all, we will see what questions theorists are interested in answering, how questions are answered in theory, and the deep foundation theory creates for the field of computer science.

Students who complete this course are expected to be able to:

• Apply mathematical concepts, especially proof techniques, to problems in theoretical computer science.
• Identify languages at different levels of the Chomsky hierarchy.
• Design appropriate finite state machines to recognize different languages.
• Analyze the limits of different computational models such as finite automata, pushdown automata, or Turing machines.
• Describe examples of problems at each level of computability and complexity.
• Explain computability, complexity, undecidability, and NP-completeness at various degrees of technical detail.
• Argue formally whether a problem admits efficient solutions using theory of computation proof techniques.
• Communicate theory of computation concepts effectively through different media, such as writing formal proofs, drawing representations of computational models, and presentations of proofs.
• Develop the practice of providing feedback for others’ proofs and arguments.
• Work collaboratively with partners or small groups to solve theory of computation problems.

Textbook

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

Course Requirements

• Class meetings: Class meets twice per week.
  • The course website links, for each lecture, to slides representing a notes-outline that we will be filling out together, in class.
  • If you miss a class for some reason, you are responsible for studying the notes-outline on the course website, asking for notes from a peer, and reading the corresponding reading from the text. If you have questions about the material, you should see the instructor during regular office hours.
  • Phones and laptops are not allowed during class time. This is to help us all focus on the concepts we're learning, be present as a community, and practice the skills the course is built on.
  • Each class' notes-outline contains the corresponding book chapters for the material covered.
• Class videos: Videos are available to introduce many but not all topics.
  • Videos should be watched before the corresponding class so that you come to class prepared to engage in activities based on material presented in the video.
  • Videos usually have corresponding quizzes. The quiz corresponding to a video should be taken after watching the video and before coming to class.
• Quizzes: Many classes have videos that introduce new material, and most of these videos have corresponding quizzes. Before class, you should watch the video and then take the quiz. The purpose of each quiz is to help you assess your understanding of the most recent material. If there are any questions that you do not answer correctly, that is a sign that the material covered needs to be revisited, either on your own or during office hours. You may take a quiz as many times as you like and only your highest score on that quiz will be retained.
• Assignments: During the term, there will be regular homework assignments. You must complete these individually.
  • Assignments are due at the beginning of class (at 8:30am) on the due date indicated in the course calendar. There are no extensions.
  • Solutions will be handed out in class. Each assignment is graded on a completion and best effort basis (for each problem). Your lowest score will be dropped.
  • Assignments have two parts (A and B). For part A of each assignment you will receive qualitative feedback from our graders, to help you improve and grow over time. Part B of assignments 1 through 8 will be taken by a fellow classmate, who will pick one of the problems of the assignment to give you qualitative feedback on. This feedback is due when the next assignment is due, as indicated on the course calendar. Your lowest score for part B will be dropped. The target audience for giving feedback is your fellow class mate, and there is an expectation of clear, respectful, and precise language.
  • Giving and receiving feedback, as well as the inherent repeated revisiting of the same concepts are proven to help deep learning. I recommend you read both types of feedback you receive carefully and reflect on how you can apply it to other problems, in order to, over time, improve your understanding, clarity, and effectiveness, and grow in your proof writing skills.
• Module assessments: There are four module assessments this semester.
  • The course is split into four modules. There will be an assessment for each module.
  • All students are expected to be in class and take the assessments on those dates; there are no exceptions and module assessments are not subject to extensions.
  • The assessments will be in-class, will take 35 minutes, and will be closed book and closed notes.
  • Each assessment will contain one problem from a homework corresponding to that module.
  • You have the opportunity to retake the first three modules and your highest score will be considered.
  • If an emergency prevents you from completing the assessment as scheduled, we can schedule a make-up assessment 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.
• Presentations: You are expected to give two proof presentations this semester.
  • Proof presentation cover certain problems on the homework, labeled in each homework.
  • One presentation has to be on material covered in Modules 2 or 3, and the other has to be on material covered in Module 4. The deadlines are included in the calendar above.
  • Each presentation will take 8 minutes, and will be 1-1, at a time chosen by you in the available 10-min slots offered by the instructor. Since you have the freedom to choose this 10-min slot over the course of a few weeks, presentation times are reserved for you and you alone, and once selected, cannot be changed, extended, or moved.
  • The rubric used to evaluate the presentations can be found here.
  • You will have a diagnostic presentation on material covered in Module 1, that you must present on by the deadline included in the calendar.

Collaboration Policy

We believe that collaboration fosters a healthy and enjoyable educational environment. What's more, collaboration is an expected skill in the field of computer science. For this reason, we encourage you to talk with other students about the course material and to form study groups.

However, there is a thin line between collaboration and plagiarizing the work of others. 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, or from conversations during office hours or with your study group, 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 else and turn in two copies of the same solution, (2) to copy a solution written by your classmates, (3) to read another student's solution, (4) to view assignments, assessments, and solutions from previous terms of CS235, (5) to ask someone for solutions from previous terms of CS235, (6) to make any of the assignment or assessment solutions available for others online or offline, or (7) to post or look up CS235 assignment/assessment problems to stackexchange, ChatGPT, or other such resources to get help in solving the problems (if you don't know whether using a particular resource is a violation of the Honor Code, it is your responsibility to check in with the instructors before using it).

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.

Generative AI Policy

The use of LLMs or generative AI is not permitted in this course. The use of such tools in any way constitutes a violation of Wellesley's Honor Code.

Grading Policy

During the semester you will be accumulating points, for a total possible of 200 points by the end of the semester. Here are the components that you will be accumulating throughout the semester:

• Module 1 assessment: 35pts
• Module 2 assessment: 30pts
• Module 3 assessment: 35pts
• Module 4 assessment: 20pts
• Class participation (attendance, quizzes, team work, making an effort to live by class norms, and respectful engagement): 20pts
• Presentations: 30pts
• Assignments : 30pts
  • Assignments 1 through 9: 16pts
  • Peer Feedback on Assignments 1 through 8: 14pts

At the end of the semester, I will divide the total number of points each student has accumulated by 200 and assign letter grades. In general, the mapping from numerical score to letter grade 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, I may adjust this mapping.

Google Group

There is a CS235 Google Groups named CS-235-01-FA26. This group has several purposes. I will use it to make class announcements, such as corrections to assignments and clarifications of material discussed in class. I encourage you to post questions or comments that are of interest to students in the course. I 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 good places to find people to join a study group. You should plan on reading messages sent to the group on a regular basis.

Brightspace

There is a Brightspace website for our course, that you have already been added to. All your scores (assignments, module assessments, presentations) will be included there.

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.

Religious Observance

Students whose religious observances conflict with scheduled course events should contact the instructors in advance to discuss alternative arrangements. You may do this through the Wellesley College Religious Observance Notification System if you prefer.