Spring 2019 CS235
Welcome to CS235, an introduction to the theory of computation
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.
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.
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:
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.
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.
There is a CS235 Google Group named
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.
If you have a disability or condition, either long-term or temporary, and need reasonable academic adjustments in this course, please contact Disability Services 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 Disability Services. They can provide assistance including screening and referral for assessments.
Disability Services can be reached at firstname.lastname@example.org, 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.
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; email@example.com). 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.