Theory of Computation (CS3800 12S) homepage

You have reached the webpage for the Northeastern University, College of Computer and Information Science, Spring 2012 session of Theory of Computation, also known as "CS3800 12S." This is an undergraduate course on the theory of computation. It serves as an introduction to formal models of languages and computation. Topics covered include finite automata and regular languages, pushdown automata and context-free languages, Turing machines, computability, and NP-completeness.

This course meets 1:35 pm - 3:15 pm TF West Village H 110
The instructor is Emanuele Viola. Email: (instructor's five-letter last name)
Office hours, West Village H 246.
Part-time Teaching Assistant: Eric Miles, West Village H 266. Office hours: held in the lounge outside room 208 Thursday 11 - 12:30. Email:

This page, especially the problem sets below, will be modified from time to time; be sure to reload documents on occasion and check the "last modified" date against any printed version you may have.


Announcements, including problem sets

2012-02-10 Friday QUIZ 1.

2012-03-02 Friday QUIZ 2.

2012-03-13 Tuesday Mid-course survey.

2012-03-30 Friday QUIZ 3.

2012-04-20 Friday Extra office hours 1:35 pm - 3:15 pm.

2012-04-23 Monday QUIZ 4, 8:00 am - 10:00 am, Shillman Hall 105

Quiz sample.

Note: You should pick up your graded homework and quizzes during the TA's office hours. This gives you an opportunity to discuss solutions and any corrections.

Note: The next exercises refer to the textbook Introduction to the Theory of Computation, Second Edition, by Michael Sipser.

Problem Set 1. Assigned on 1/20, due on 1/27.
1: Exercise 1.6 parts: b, c, d, and e.
2: Give the formal definition of the DFA pictured in Exercise 1.21, (b). Show that this DFA accepts the string aab using the formal definition of accepting seen in class. For your reference, this definition is on Slide 45 and also in the book on Page 40.

Problem Set 2. Assigned on 1/27, due on 2/3.
1: Exercise 1.16.
2: Exercises 1.8 part a, 1.9 part a, and 1.10 part a.

Problem Set 3. Assigned on 2/17, due on 2/24.
1: Exercise 1.21.
2: Exercises 1.29(b).
3: Use the pumping lemma for regular languages to show that the following language is not regular: L = {ai b j | i > 3j }.
4: Exercise 2.4, part b, part c, and part e.
5: Exercise 2.9.
6: Consider the following CFG grammar: S -> aSaS | aSa | ε. Show that the grammar is ambiguous.

Problem Set 4. Assigned on 3/16, due on 3/23.
The next exercises refer to the file Quiz sample.
22: (b) and (c).
27: (c) and (d).
34: (a) and (e).
36: (b).

Problem Set 5. Assigned on 4/6, due on 4/13.
The next exercises refer to the file Quiz sample.
39: (c) and (d).
46: (d).
47: (e).

Course outline

Note: Slides will be updates throughout the course. Make sure you have the last version.

Overview of class.
Slides .PDF, .ODP.

Math primer. Reading: Sipser Chapter 0. Think like the pros, sections 1,2, and 4.4.
Slides .PDF, .ODP.

Regular languages and finite automata. Reading: Sipser Chapter 1.
Slides .PDF, .ODP.

-regular operations
-closure properties
-equivalence of NFAs and DFAs
-regular expressions
-equivalence of RE and FA
-the pumping lemma

Context-free languages and pushdown automata. Reading: Sipser Chapter 2.
Slides .PDF, .ODP.

-context-free grammars
-pushdown automata
-equivalence of CFLs and PDAs
-pumping lemma for CFLs
-closure properties

Turing Machines and Computability. Reading: Sipser Chapter 3, 4, 5, and Problem 5.28.
Slides .PDF, .ODP.

-Turing Machine variants
-Church-Turing thesis
-cardinality of infinite sets
-Halting Problem
-Rice's theorem

Complexity. Reading: Sipser Chapter 7.
Slides .PDF, .ODP.

-P and NP
-the Cook-Levin Theorem

Course information


As important, perhaps, is the material from CS1800, Discrete Structures, which itself is a prerequisite for CS2800.


Errata for this text are available on-line. If you are concerned that something in the text might be a typo, please check the errata available here: Errata for Introduction to the Theory of Computation, Second Edition, by Michael Sipser.


Problem sets should be placed in the "CS 3800" box in front of room West Village H 266 by the start of class on the due date.

When solving a problem you can use all the results seen in class. You should not use other sources. I want you to spend your time thinking about the problems, not searching for a solution on the web.

Some of the exercises will be routine, but others will be more challenging. I do not expect you to solve all of the homework problems, but I hope that you will benefit from working on the more difficult ones. A few hints on the homework assignments:


Your final grade is calculated as follows: There will be about 4 quizzes. The last quiz will be held during exam week. The other quizzes will be held during regular class times. Half of your least-scoring quiz will be "dropped." That is, it will not count towards your final grade. Quizzes are "closed-book." You cannot bring any book, notes, or electronic device.

Your least-scoring problem-set will also be "dropped." That is, it will not count toward your final problem-set grade.