Course notes for CS154

This file will keep track of the material covered so far, and list the hand-outs and homeworks distributed to date.

Preliminaries

Chapter 0.1 of the book tells you where this course will be about. Read it before taking this class, together with the first section of the preface. The rest of Chapter 0 consist of preliminaries that you should have encountered in CS103 or other courses. Please leaf through this chapter to check that you are acquainted with its contents. Ask us for help if necessary, preferably prior to the first class. During the first lecture homework has been assigned on this material. It is due on Wednesday January 17, at the beginning of class.

Wednesday, January 10

I presented a short overview of the course and made a start with Chapter 1, reaching roughly page 54 of Sipser. Homework on this section has been handed out (but the version linked here is an improvement and simplification of the one handed out).

[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.]

Monday January 15 is a holiday.

Wednesday, January 17

I showed that DFAs, NFAs (with epsilon-transitions) and regular expressions describe the same languages. Thereby most of Chapter 1 has been covered. Only the pumping lemma and minimization of DFAs is left for next week. More homework has been given.

Monday, January 22

I finished the treatment of regular languages with the pumping lemma (the main tool for showing that certain languages are not regular) and a technique for making sure that a DFA has as few states as possible. The latter (minimization) is not covered in Sipser. Therefore a handout has been distributed (available from the handout hang out). The essence of the matter is here.

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

Wednesday, January 24

"Repairing" ambiguous grammars; inherently ambiguous languages; Chomsky normal form; regular languages are context free.
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 homework should be done without collaboration!

Monday, January 29

Pushdown automata, and their equivalence with context-free grammars. Deterministic pushdown automata.
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.

Wednesday, January 31

I finished the conversion from PDAs to CFGs (started on Monday) and then treated the 3 algorithms linked below. Finally I mentioned a few undecidable problems regarding Context-free languages (see below). Homework 4 (also in pdf) has been put on the web and in the handout hang out.

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.
On the other hand, there are no algorithms whatsoever for
- 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.

CS154N

This part of the course deals with Parts Two and Three of the book.

Monday, February 5

Today I discussed Church's thesis and gave a treatment of decidability without using Turing machines and Church's thesis, following this handout. This corresponds with Sipser Chapter 4 (and Theorem 3.3), although there the material is phrased in terms of Turing machines. Please read the handout carefully before the next lecture.

Wednesday, February 7

I treated Turing machines, and their connection (through Church's thesis) with decidability. I showed that a multi-tape Turing machine can be simulated by a standard one-tape Turing machine, and that nondeterministic Turing machines are just as powerful as deterministic ones.
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 reducing one problem to another to show (un)decidability (see the handout). This corresponds with Sipser pages 171-173.
Homework 5 (also in pdf) has been put on the web and in the handout hang out.

Monday, February 12

I introduced the method of diagonalization, and used it to show that the real numbers are uncountable, i.e. there are more real numbers than natural numbers. I rephrased the proof from the handout that there exists an unrecognizable language in term of diagonalization. It was also observed that there are more languages than algorithms.

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.

Wednesday, February 14

Today I proved the undecidability of the emptiness problem for linear bounded automata, and of the Post correspondence problem. I briefly touched on context-sensitive languages. Homework 6 (also in pdf) has been put on the web and in the handout hang out.

Monday February 19 is a holiday.

Wednesday, February 21

Today I treated 3 subjects that are not covered in Sipser: the undecidability of the empty intersection problem and the ambiguity problem for context-free grammars; Rice's theorem and the undecidability of first order logic. Homework 7 (also in pdf) has been put on the web and in the handout hang out.

Monday, February 26

Today I treated the n-ary and n-adic representation of natural numbers as strings. The latter provides a perfect 1-to-1 correspondence between strings over a n-letter alphabet and the natural numbers. The concepts of decidability and enumerability now apply not only to languages but also to sets of natural numbers. Then I proved the undecidability of arithmetical truth, and Goedel's incompleteness theorem, following this handout. Do read. Finally I introduced the class of arithmetical languages, which properly extends the recursive enumerable ones. (I also mentioned the even larger class of analytical languages.)

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.

Wednesday, February 28

I introduced, for every function f(n) on the length n of the input string, the complexity classes TIME(f(n)) and NTIME(f(n)). These give worst case upperbounds for the time it takes to solve a problem on a deterministic, respectively nondeterministic, Turing machine. The class TIME(f(n)) is included in NTIME(f(n)). Moreover, if L is in NTIME(f(n)), then there is a constant k such that L is in TIME(k^f(n)). I also introduced the classes P and NP and told that it is a famous open problem whether P = NP. Most computer scientists think this is not the case. Homework 8 (also in pdf) has been put on the web and in the handout hang out.

Monday, March 5

I explained that the class NP can be seen as the class of problems with polynomial time verifiers, and showed that the problems Hamiltonian Path and Non-primes are in NP. I introduced the concept of a polynomial time reduction, also telling the difference between mapping reductions (also called many-one reductions) and general (or Turing) reductions. In passing I mentioned the notions of computable (or recursive) and partial recursive functions. Then I explained the notion of NP completeness.

Wednesday, March 7

I treated NP-completeness and NP-hardness, sketched the proof that SAT, and even 3SAT is NP-complete, and established the NP-completeness of Clique by means of a polynomial time reduction from 3SAT to Clique. In the book, there are many more NP-complete problems, which are assigned reading. Showing NP-completeness is a skill that is a vital part of this course, and you should practice on your own to get the necessary experience. Chapter 7, on time complexity, is now considered to be covered in full, except for the small-o notation, and Theorems 7.13 and 7.14.

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.

Monday, March 12

I showed that the class of context-free languages is included in P (Sipser Thm. 7.14). That the problem of determining whether two numbers are relatively prime is in P (Thm. 7.13) you can read in the book.

Then I proved Savitch's theorem, saying that if f(n) log(n) then NSPACE(f(n)) SPACE(f(n)²). 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.

Wednesday, March 14

I discussed the hierarchy of complexity classes

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