CSE 105: Automata and Computability Theory
Autumn 2012
Overview
Announcements

The final exam will be closed book. However, you will be
allowed to bring in one sheet of paper,
8½″×11″, handwritten—not printed or
photocopied—filled on both sides with any information you
think you’ll need.

Prof. Shacham’s office hours are canceled on Wednesday,
November 7th. He will hold makeup office hours on Friday,
November 9th, 1:00–4:00 PM, in his office.

Monday, November 12th is Veterans’ Day, a holiday. Office
hours and lecture will not be held that day. (The same holds for
office hours and section on Thursday and Friday of Thanksgiving
week, November 22nd and 23rd.)

Theresa’s office hours are canceled on Tuesday, October 23rd.

There will be no section on Friday, September 28th. The first
class meeting will be Monday, October 1st.

There is a third edition of Sipser’s book, but we will be
using the second edition, which has everything we need and is much
more affordable. We will read only chapters 1 through 5; you
should be able to obtain a facimile edition of just these chapters
from the bookstore for around $60. Alternatively, consider used
copies available at
Amazon and
elsewhere.
Exercises
You may collaborate with as many other students in the class on the
exercises. You should write up your solutions on your own.
Exercises are collected in class and checked off for completeness
but not graded.
 Exercise #1:
Hammack §1.1 4,15,25;
§1.2 1(a)–(e);
§1.3 4,5;
§1.4 15,16;
§1.5 9;
§1.6 2;
Hammack §2.1 4,5,6;
§2.2 1,7;
§2.5 10;
§2.7 8;
§2.10 3.
Collected: Wednesday, October 3rd, 2012, 6:30 PM.
 Exercise #2
Hammack §4 5,7,16,26;
Sipser 1.2, 1.3, 1.4d, 1.4e, 1.6i, 1.6k, 1.6n, 1.7a, 1.7d.
Collected: Wednesday, October 10th, 2012, 6:30 PM.
 Exercise #3
Hammack §5 4,11,15,18;
Sipser 1.15, 1.19, 1.20, 1.40, 1.44.
Collected: Monday, October 22nd, 2012, 6:30 PM.
 Exercise #4
Hammack §6 8,9,16;
Sipser 2.2, 2.4a, 2.4b, 2.4d, 2.6a, 2.6b, 2.15.
Collected: Monday, October 29th, 2012, 6:30 PM.
 Exercise #5
Hammack §7 9,16,17;
Sipser 3.1b, 3.2a, 3.5, 3.7, 3.8c
Collected: Wednesday, November 14th, 2012, 6:30 PM.
 Exercise #6
Hammack §8 4,5,11,22;
Sipser 3.15a, 3.15c, 4.1, 4.2, 4.4, 4.9, 4.11, 4.13
Collected: Wednesday, November 28th, 2012, 6:30 PM.
Problem Sets
You must solve the problem sets on your own, without
discussing them with anyone. You must write up your solutions on
your own. Problem sets are collected in class and graded for
correctness. Think of them as takehome, openbook midterms.
 Problem set #1:
download as a PDF.
Due: Monday, October 15th, 6:30 PM.
 Problem set #2:
download as a PDF.
Due: Monday, November 5th, 2012, 6:30 PM.
 Problem set #3:
download as a PDF.
Due: Monday, November 19th, 2012, 6:30 PM.
 Problem set #4:
download as a PDF.
Due: Monday, December 3rd, 2012, 6:30 PM.