Reading

Nils Anders Danielsson

The reading list currently includes the following documents:

B: The main text book, “Introduction to Automata Theory, Languages, and Computation: Pearson New International Edition, 3/E” by Hopcroft, Motwani and Ullman (ISBN-10: 1292039051, ISBN-13: 9781292039053). Chalmers students can access the book online via Chalmers’ library, but it is unclear to me if there are any restrictions as to, say, how many persons can access the book simultaneously.
MCS: The book Mathematics for Computer Science by Lehman, Leighton and Meyer.
P: Koen Claessen’s notes on proof methods.
S: Koen Claessen’s notes on structural induction.
I: Ana Bove’s Notes on Inductive Sets and Induction.
PL: Ana Bove’s Notes on Pumping Lemma.
SP: A Very General Method of Computing Shortest Paths by Russell O’Connor.
R: Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, …) by Russ Cox.

The reading list (this list might be updated during the course):

Week	Lecture	Reading
1	1	Nothing.
	2	MCS 1.1–1.2, 3–4. (Not III–IV.)
	3	B, the box “How Formal Do Proofs Have To Be”. MCS 1, 5–5.2.1, not 5.1.5. P. I 1–2, 4–5, not 1.2.3 or 4.2.
2	4	S. I 3. B 1 (optional: 1.2–1.4).
	5	B 2–2.2.
	6	B 2.3–2.3.5, 2.4.
3	7	B 2.3.6, 2.5.
	8	B 3.1, 3.2–3.2.2. Optional: 3.2.1, SP.
4	9	B 3.2.3, 3.4, 4–4.2.1. PL 1.
5	10	B 4.3–4.4. Optional: R.
	11	B 5–5.2.2. I 1.2.3, 4.2.
6	12	B 5.2.3–5.2.6, 5.4.
	13	B 7.1–7.2. PL 2.
7	14	B 7.3-7.3.4 (not the proof of Theorem 7.27, not Example 7.28), 7.4 (not 7.4.1).
	15	B 6.1-6.2.1, 8.2 (not 8.2.4).
8	16	Nothing.
	17	Nothing.