Office Hours: Tuesday and Thursday, 3:00–5:00 and by appointment, Sanders Physics 305

Tuesday & Thursday, 9:00–10:15 a.m., Sanders Physics 105

This course introduces students to the theory of computation, the
mathematical foundation of computer science. We will consider what is an
appropriate mathematical model of a computer, what types of computations are
possible in the model, what types are not, the inherent complexity of certain
computations, etc. Although considering computers as abstract mathematical
objects may on the surface seem unrelated to “real” computing, in
fact many concepts you will encounter are fundamental to important areas of
computer science, including compiler design, hardware design, object-oriented
design, computational linguistics, and even the syntax of the
UNIX `grep`

and `awk`

commands.

During the course, you will gain an understanding of the intimate connection between computation and language recognition. We will study several classes of abstract machine including finite automata, push-down automata, and Turing machines, along with several classes of languages such as regular and context-free languages. In addition, we will look at problems like the Halting Problem that are not amenable to a computer solution.

The course provides essential background for CMPU 331, Compiler Design: ideally, you should take CMPU 331 in the semester immediately following completion of this course.

Prerequisites: CMPU 102 and CMPU 145.

The calendar on this page will be updated throughout the semester with readings, assignments, and exams. Schedule a reminder to check it after each class.

The assigned chapters should be read before the corresponding class. You are responsible for keeping up with the reading and for all material covered in class (some of which may not be in the book). This includes classnotes, assignments, handouts, additional readings, etc. If you miss a class for any reason you are responsible for making arrangements with classmates to provide you with all information disseminated in class that day.

Week | Tuesday | Thursday |
---|---|---|

## 0 |
## Sep. 4Course information Review of mathematical concepts and proof techniques Read Chapter 0. |
## Sep. 6Read Section 1.1. |

## 1 |
## Sep. 11Nondeterministic Finite automata Read Section 1.2. |
## Sep. 13Read Section 1.3. |

## 2 |
## Sep. 18 |
## Sep. 20Pumping Lemma, non-regular languages Read Section 1.4. |

## 3 |
## Sep. 25 |
## Sep. 27 |

## 4 |
## Oct. 2Exam 1 review Handout: Exam 1 Topics Slides: Practice proofs |
## Oct. 4Read 2.1. |

## 5 |
## Oct. 9Read 2.2. Assignment 4 out |
## Oct. 11 |

The primary textbook for this course is Introduction to the Theory of Computation, third ed., by Michael Sipser (2012).

There will be occasional supplemental readings made available on this website or distributed in class.

You are responsible for completing all assigned readings before the class indicated in the schedule on the webpage, whether or not the material is covered in lectures. (Exception: The readings for the first day. Don’t panic.)

One goal of this course is to develop your facility to manipulate language formalisms, so completion of weekly assignments is extremely important.

Assignments and due dates will be listed in the calendar, above. All assignments are due at the beginning of class on the indicated days and should be turned in directly to me.

When computing your final grade for the course, your lowest homework score from among the homeworks that were turned in – on time or late – will be dropped.

As with all policies, homework policies are intended to be fair to everyone involved in the course. They will be enforced fairly. Please feel free to ask me any questions about specific cases that may emerge over the semester.

Each problem will be graded along the following lines:

- Didn’t do anything
- Incomplete or mostly incorrect.
- More or less incorrect but you are on the right track; or correct but is muddled in the argument.
- Correct logic and written coherently. Might have a missing step or two.
- Wow! I think you really get it.

Note that strong effort as you get better will make up for poorer performances in previous weeks.

**NB**: Neatness counts! Two points (on the 0–4 scale)
will be automatically deducted from any assignment that does not meet the
following requirements:

- Show all the steps used to arrive at your solution.
- Indicate your final solution clearly.
- Put your name and the assignment number / page number at the top right corner of all pages – e.g., “Assn. 1/1”, “Assn. 1/2”, etc.
- Type your work or write legibly on 8½×11″ lined paper.
- Hand in clean copy – i.e., don’t hand in messy work where bits have been crossed out, etc.
- Staple papers together in the top left corner.
- Do not hand in paper with frayed edges torn from a notebook.

You are encouraged to prepare your assignments using the typesetting language LaTeX, which is a standard tool for publishing research in computer science. To get started, you can refer to Getting Started with LaTeX, go to this list of LaTeX tutorials, or simply enter “latex tutorial” in a search engine to see many other links.

A LaTeX assignment template is available.

I recommend using Overleaf online so you don’t need to install anything and you can get an instant preview of your work. (I use Tectonic, but that’s a non-standard choice.)

Full solutions to all problems will be posted on the course webpage when graded assignments are returned. Exercises and problems in our textbook that are prefaced with an “A” have solutions at the end of each chapter. Be sure you understand all the book solutions as well as the assigned problems.

Permitted, but if you do cooperate, the solutions must be written up individually (not copied). If you cooperate with another student, indicate this on your assignment.

Receiving and copying solutions from any source (a classmate, a friend, a published text, an online source, etc.) is disallowed. Note that using material from sources (other than those explicitly given as course resources) as “inspiration” and submitting highly derivative solutions is viewed as copying. (Please read Going to the Source: A Guide to Academic Integrity and Attribution at Vassar College, available from the Dean of the College website.) Inappropriate use of sources (including people) will be reported to the Academic Panel.

There will be three exams. The first two focus on lectures and readings from the immediately preceding segment of the course. The third exam will focus primarily on later material but may also include material from earlier in the course.

The first two exams may be take-home.

Note that we may not cover all the assigned reading in class, but you are responsible for all assigned readings and all material covered in class for the exams.

The elements of the course will be weighted as follows when determing your overall grade:

Written Assignments | 40% | (About eight problem sets) |

Exam I | 20% | |

Exam II | 20% | |

Exam III | 20% |

An optional programming assignment may be done for extra credit.

This course includes a lot of detailed information that supports the “big ideas” that we will gain an understanding of during the course. Here are some suggestions for approaching the course material and lectures that can help guarantee that you get the most out of it.

- Read the required material
*before*the class where it will be presented. This way, you are reinforcing what you already understand with another explanation. If you come to class without the reading, the material will be very hard to absorb in one sitting. - Start the assignments a couple of days before they are due. The problems are the kind that can benefit from going away and coming back later when you are stuck.
- Study and do assignments with others from the class when you can. Obviously, your assignments should reflect your own work, but getting an explanation of a concept from a peer is often an effective way to make it sink in.
- Focus on the main concepts and not just the details. For example, don’t just memorize the steps to convert a DFA to an NFA, but understand how the conversion works in principle. The steps then become easy to remember.
- Talk to me if you have any questions! I am here to help.

Academic accommodations are available for students registered with the Office for Accessibility and Educational Opportunity (AEO). Students in need of disability (ADA/504) accommodations should schedule an appointment with me early in the semester to discuss any accommodations for this course that have been approved by the Office for Accessibility and Educational Opportunity, as indicated in your AEO accommodation letter.

Vassar College is committed to providing a safe learning environment for all students that is free of all forms of discrimination and sexual harassment, including sexual assault, relationship abuse, and stalking. If you (or someone you know) has experienced or experiences any of these incidents, know that you are not alone. Vassar College has staff members trained to support you in navigating campus life, accessing health and counseling services, providing academic and housing accommodations, helping with legal protective orders, and more.

Please be aware all Vassar faculty members are “responsible employees,” which means that if you tell me about a situation involving sexual harassment, sexual assault, relationship abuse, or stalking, I must share that information with the Title IX Coordinator. Although I have to make that notification, the Title IX office will only provide outreach by email. You will control how your case will be handled – you don’t have to read or respond to the email, and it is completely up to you whether to pursue a formal complaint. Our goal is to make sure you are aware of the range of options available to you and have access to the resources you need.

If you wish to speak to someone privately, you can contact any of the following on-campus resources:

- Counseling Service (845-437-5700)
- Health Service (845-437-5800)
- Nicole Wong, SAVP (Sexual Assault and Violence Prevention) director (845-437-7863)
- SART (Sexual Assault Response Team) advocate, available 24/7 by calling the CRC at 845-437-7333 and asking for SART

The SAVP website and the Title IX section of the EOAA website have more information, as well as links to both on- and off-campus resources.

- JFLAP: Graphic tool that does conversions from nondeterministic finite automaton (NFA) to deterministic finite automaton (DFA), DFA to minimum state DFA, NFA to regular grammar, regular grammar to NFA, nondeterministic pushdown automaton (NPDA) to context-free grammar (CFG), and three algorithms for CFG to NPDA. JFLAP is downloadable for free.
- Turing Machine Simulator: JavaScript version by David Eck.