CMPU 240

Language Theory and Computation

Fall 2018

Instructor

Jonathan Gordon

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

Lectures

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

Overview

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.

Calendar

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

Course information

Review of mathematical concepts and proof techniques

Read Chapter 0.

Sep. 6

Finite automata

Read Section 1.1.

1

Sep. 11

Nondeterministic Finite automata

Read Section 1.2.

Assignment 1 (Solutions)

Sep. 13

Regular expressions

Read Section 1.3.

2

Sep. 18

Regular expressions (cont’d)

Assignment 2 (Solutions)

Sep. 20

Pumping Lemma, non-regular languages

Read Section 1.4.

3

Sep. 25

Non-regular languages

Sep. 27

DFA minimization

Read Hopcroft et al. (3rd ed.), section 4.4

Assignment 3 (Solutions)

4

Oct. 2

Exam 1 review

Handout: Exam 1 Topics

Slides: Practice proofs

Exam 1 (Solutions)

Oct. 4

Context-free grammars

Read 2.1.

5

Oct. 9

Pushdown automata

Read 2.2.

Assignment 4 out

Oct. 11

Pushdown automata, continued

Textbook

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

Assignments

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.

Assignments received after the beginning of class will be considered late. Late assignments can be given to me in class or left in the slot outside my office, SP 305. Assignments turned in one day late lose 15%. Assignments turned in two days late lose 25%. Assignments turned in more than two days late will be a 0, but you should still turn them in so you get the practice and you get feedback on your work.

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:

  1. Didn’t do anything
  2. Incomplete or mostly incorrect.
  3. More or less incorrect but you are on the right track; or correct but is muddled in the argument.
  4. Correct logic and written coherently. Might have a missing step or two.
  5. 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:

LaTeX

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.

Cooperation policy

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.

Academic integrity

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.

Exams

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.

Course Grades

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.

How to Succeed in CMPU 240 by Really Trying

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.

Academic Accommodations

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.

Title IX

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:

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.

Interesting Links