[For the readers of Hopcroft, Ullman and Motwani (HMU): we would have reached Section 2.3.4 now. Our NFAs are the NFAs with epsilon transitions treated in HMU Section 2.5.]

**Covered material on regular languages**: Sipser Chapter 1 (all of
it) and minimization of DFAs
(not in Sipser).

This corresponds to HMU Chapter 2 (except 2.4) and Sections 3.1, 3.2,
4.1, 4.2.1 and 4.4.

Important topics:

- DFAs and NFAs recognize, and regular expressions generate, the same
class of languages, called the
*regular languages*. - These languages are closed under intersection, union, concatenation, star, complement and reversal.
- The pumping lemma and the closure properties are the main tools for showing languages to be non-regular.
- There are easy algorithms for

Then we introduced context-free languages, treating Context-free grammars, parsing, and ambiguity. This corresponds with Section 2.1 from Sipser, or Chapter 5 from HMU (skipping Section 5.3).

Showing that certain languages are not context-free: the pumping lemma for context-free languages and intersection with a regular language.

Homework 3 (also in pdf) has been handed out.

The material on useless variables and algorithms linked below is assigned reading for Wednesday. It may be helpful when reviewing your solution to problem 4 of homework 3.

**Covered material on context-free languages**: Sipser Chapter 2 (all of
it) and the concept of useless variables
(not in Sipser).

This corresponds to HMU Chapters 5, 6 and 7, except Sections 5.3, 6.4,
7.3.1, 7.3.2, 7.3.5 and 7.4.

Important topics:

- Context-free grammars generate, and pushdown automata recognize, the
same class of languages, called the
*context-free languages*. - These languages are closed under union, concatenation, star and reversal, as well as intersection with a regular language. They are not closed under complementation and intersection.
- The pumping lemma and the closure properties are the main tools for showing languages to be non-regular.
- Parsing, ambiguity, inherently ambiguous languages.
- There are easy algorithms for
- eliminating epsilon-productions and unit rules, and converting a CFG into Chomsky normal form,
- eliminating useless variables from a CFG,
- checking whether a pushdown automaton or CFG accepts a given string,
- and checking whether the language accepted by a given pushdown automaton or CFG is empty.

- checking whether two CFGs generate the same language,
- checking whether the intersection of two context-free languages (given by CFGs or PDAs) is empty,
- and checking whether the language accepted by a given pushdown automaton or CFG consists of all strings over the given alphabet (i.e. whether its complement is empty).

The midterm exam (on Friday, Feb 9 from 2:45 to 5:15pm) covers all the material on regular and context-free languages mentioned above. It is an open book exam.

All the material of Sipser Chapters 3 and 4 is now considered covered; you are advised to examen these chapters yourself to get a feeling for certain details that where not spelled out in class. Also in Chapter 4 you can see what form some elements of my handout on decidability take when formulated in terms of Turing machines. In class I didn't treat the uncountability of the real numbers by the method of diagonalization; you are advised to read this in the book.

In addition I introduced the concept of

Homework 5 (also in pdf) has been put on the web and in the handout hang out.

Next I explained the notion of a reduction, and the direction in which to apply it. I showed that it is undecidable whether a given Turing machine accepts the empty language, by reducing the acceptance problem (which is known to be undecidable) to it. This is a special case of Rice's theorem, which says that any nontrivial property about the language recognized by a Turing machine is undecidable.

**Covered material on computability theory**: Sipser
Chapters 3, 4, 5 (except the proof of theorem 5.10), 6.2 (except for
Theorems 6.10 and 6.15) and 6.3, as well as the handouts linked (or
listed) below.

This corresponds to HMU Chapters 8 and 9, except Sections 8.5.3, 8.5.4
and 9.5.3, plus the handouts.

Important topics:

- Decidable, recognizable and enumerable languages; recursive, Turing-recognizable and recursive enumerable languages; the relationships between these classes; Church's thesis.
- The decidable languages are closed under union, intersection and complementation; r.e. languages under union and intersection, but not complementation.
- The existence of unrecognizable languages, and of recognizable but undecidable languages. Diagonalization. Countability.
- Turing machines; configurations; multitape TMs; the equivalence of deterministic and nondeterministic TMs.
- Computable (or recursive) and partial recursive functions.
- The method of reduction. Undecidability of the acceptance problem for TMs, the halting problem, whether an algorithm halts on all inputs, the emptiness problem for TMs, the emptiness problem for LBAs, Post Correspondence Problem, ambiguity of CFGs, empty intersection of CFGs, provability in first order logic and truth in arithmetic.
- Rice's theorem.
- n-adic and n-ary representation of natural numbers (there is a paper handout in the handout hang out).
- Goedel's incompleteness theorem and the class of arithmetical languages.

Subsequently I made a start with space complexity, following this handout.

The last homework (also in pdf) has been put on the web and in the handout hang out. It is due on Monday March 12, 3:15pm. Better finish it before dead week starts. Homework classified as late will be accepted until Wednesday 3:15pm this week.

Then I proved Savitch's theorem, saying that
if f(n) log(n) then NSPACE(f(n))
SPACE(f(n)^{2}).
I also showed that if L is in SPACE(f(n)) with f(n) log(n), then there is a constant d such that L is in
TIME(d^{f(n)}). Subsequently I introduced PSPACE-completeness
and sketched the proof that the problem of determining the truth of
quantified boolean formulas is PSPACE-complete. You can read about
other PSPACE-complete problems in the book.

L NL P NP PSPACE = NPSPACE EXPTIME EXPSPACE.

Furthermore coNP sits between P and PSPACE, and coNL equals NL.I treated log-space reductions and showed that the problem of finding out whether there is a path between two given nodes in a graph is NL-complete. This also proves that NL is included in P.

I sketched a proof of the Space Hierarchy Theorem, roughly saying that all space complexity classes that could be different are different. I also discussed the corresponding Time Hierarchy theorem, but without proof.

**Covered material on complexity theory**: Sipser Chapters 7 (all
of it), 8 (except for the proof of Theorem 8.22) and 9.1 (except for
the proof of Theorem 9.10, and theorem 9.15), as well as the handout
on complexity classes.

This corresponds to HMU Chapters 10 and 11.1-3, plus the handout.
The material on the classes L and NL is not in HMU; students who are
not in the possession of Sipser should collect a copy of those parts.

Important topics:

- The complexity classes TIME(f(n)), NTIME(f(n)), SPACE(f(n)) and NSPACE(f(n)), and their relationships.
- The classes L, NL, coNL, P, NP, coNP, PSPACE, NPSPACE, EXPTIME and EXPSPACE and their relationships.
- The relationship between the classes of regular and context-free languages and the classes above.
- Polynomial time reductions and the notions of NP-completeness, PSPACE-completeness and EXPTIME-completeness.
- Log-space reductions and the notion of NL-completeness.
- The problems SAT, 3SAT, Clique, directed and undirected Hamiltonian path, and node-cover (or vertex-cover) are NP-complete; PATH is NL-complete and in P. QBF is PSPACE-complete.
- The time and space hierarchy theorems.

Sriram will do a review session Tuesday evening March 20 from 6pm to 8:30 in Gates 104. This room is reachable through the student entrance, above the round steps.

The final exam is on Thursday, March 22 from 12:15 to 3:15pm in Building 320; room 105. Like the midterm, it is open book and open notes. It covers the material on computability theory and complexity theory listed above. The material on regular and context-free languages thought earlier in this course (and tested on the midterm exam) should be still in your mind as background knowledge (as should be the case throughout your computer science studies and beyond), but it will not be tested on a very technical level.

Rob van Glabbeek | rvg@cs.stanford.edu |