Spring 2019 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.

Meet the professor


Brian Tjaden

Office location: Science Center E106

Office hours: Mondays 9:45-11:15am,
Wednesdays 11:00am-12:30pm

CS235 Spring 2019 schedule

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






Jan 29

Jan 30

Feb 1

Feb 18

Presidents' Day

Feb 20

Feb 22

Feb 25

Midterm Examination 1

Feb 26

Feb 27

Mar 1

Mar 12

Mar 13

Mar 15

Mar 19

Mar 20

Mar 21

Spring Break

Mar 22

Spring Break

Mar 25

Spring Break

Mar 26

Spring Break

Mar 27

Spring Break

Mar 28

Spring Break

Mar 29

Spring Break

Apr 15

Patriots' Day

Apr 16

Apr 17

Apr 19

Apr 22

Midterm Examination 2

Apr 23

Apr 24

Apr 26

Apr 30

May 1

Ruhlman Conference

May 3

May 7

May 8

May 9

Where do we go from here?

Assignment 9 due

May 10

May 13

Reading Period

May 14

Reading Period

May 15

Final Exams

May 16

Final Exams

May 17

Final Exams

May 20

Final Exams

May 21

Final Exams

May 22

May 23

May 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 the start of class 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. Timely submission of assignments also helps us grade and return assignments prompty. For these reasons, excepting the lateness coupons described below, we cannot accept late assignment submissions. In extenuating circumstances (e.g., sickness, personal crisis, family problems, religious holidays), you may request an extension. We will often require that an extension request be made on your behalf by your dean.

In order to offer some amount of flexibility and exception to the above policy, we offer five lateness coupons to be used at the discretion of each student:

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.

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-SP19. 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.

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/disability , 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, Sonia Jurado (781-283-2451; sjurado@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.