- Lecture 1: Our course on Theory of Computing here at Waterloo
is a "traditional" one, focusing on automata and Turing machines.
For a different approach, you might enjoy looking at the
notes of Boaz
Barak for a course at Harvard.
- Lecture 2: Post's problem is discussed, for example, in
this paper of Asveld.
For details about more recent progress on the problem, see
this paper by Neil
Sloane, starting on page 1071.
- Lecture 3: Our regular expressions in this course involve union,
concatenation, and Kleene star
*only*. Other kinds of regular expressions include "extended regular expressions", which also allow complement and intersection, and grep-style regular expressions, which allow additional operators such as backreferencing. Backreferencing allows you to specify languages that are not regular! A fun website is regular expression golf, where you try to find the shortest regular expression for a given language. - Lecture 4:
*State complexity*is a fascinating area of automata theory, where one tries to find the worst-case blowup in going from automata for regular languages*L*_{1}and*L*_{2}to automata for some function of*L*_{1}and*L*_{2}, such as their union, or from one kind of representation (say NFA) to another kind, say DFA.Suppose you start with a "randomly-chosen" NFA

*M*of*n*states. (There are many possible definitions, but let's say we choose some real number*p*and put an edge between any two states with probability*p*.) How many states do you expect to get, on average, when you do the subset construction on*M*? Nobody knows. - Lecture 5: Despite the fact that automata and regular expressions
have been studied for something like 60 years,
it was only fairly recently that people found
examples of regular expressions such that
the smallest equivalent regular
expression for the complement language is doubly-exponentially large.
See this
paper.
- Lecture 6: There are many ways to prove a language not regular.
In this course, you basically only see one: the pumping lemma.
The
Myhill-Nerode
theorem, on the other hand, gives a necessary and
sufficient condition for a language to be regular, and therefore it's
stronger and more applicable than the pumping lemma.
You learn about it in CS 462.
- Lecture 7: You can read more about Presburger arithmetic
in Sipser's book,
*Introduction to the Theory of Computation*. - Lecture 8: The software that I used for Presburger arithmetic
is called "Walnut", and it was written by Hamoon Mousavi.
It is downloadable from github,
and a user's manual is available on the
arxiv. It is pretty easy
to use, feel free to download and play around with it.
Other kinds of DFA's we did not study in 360 include the 2-way DFA and the 2-way NFA. Sometimes we cover them in 462.

I mentioned an open problem in this lecture: consider the language

*L*of primes expressed in base 2. Is*L*^{*}regular? Nobody currently knows, although everybody believes the answer is "no". If you are able to solve this, you get an automatic 100 for the course. - Lecture 9: Ambiguity is a difficult problem. We'll prove later
in the course that there is, in general, no algorithm for deciding
if a given grammar is ambiguous. And there are even
*inherently ambiguous languages*: these are languages for which every gramma is ambiguous. The first proof of the existence of such a language was carried out by Rohit Parikh in 1961. - Lecture 11:
Proving characterizations of grammars is really hard, in general.
In fact, there is no algorithm that, given two grammars
G
_{1}and G_{2}, will decide if L(G_{1}) = L(G_{2}). We might prove this later in the course. - Lecture 12: Because the class of context-free languages is not
closed under complement, people have tried to find a class larger
than the regular languages, that is closed under complement. One
such class is the class of "visibly
pushdown" languages, which
have recently been studied because they are strong enough to describe
the syntax of various markup languages.
- Lecture 13: Despite the pumping lemma for CFL's, nobody knows
whether the following language is a CFL or not (but most people believe
not):

{ x ∈ {0,1}^{*}: x ≠ y^{k}for all strings y and all k ≥ 2 } - Lecture 14: Using a PDA is often easier than using a CFG
to show that a language is context-free. For example, consider the
language L = { (a
^{n}b^{n})^{n}: n ≥ 0 }. Then the complement of L is a CFL, but this is much easier to see with a PDA than a CFG (at least for me!). - Lecture 15: Turing's original paper is
here.
It does not make for easy reading. A
whole book
is devoted to
explaining the paper line-by-line, but in my opinion your time would
be better spent reading a modern treatment of the material, as in the
course notes or textbook on reserve.
- Lecture 17: Cantor's proof of the uncountability of the
real numbers generated some controversy
when it first appeared, but by now pretty much everyone considers
it rather routine.
- Lecture 20: For more information about small Turing machines that
make a huge number of transitions before halting, see, for example,
here.
Another interesting aspect is work by Scot Aaronson, who used to teach
at UW: he and a student constructed a TM
that will run forever, unless
set theory is inconsistent!
- Lecture 23: We're just giving you a small taste of
computational complexity here. If you want more (and why wouldn't
you?), consider taking CS 489 (Complexity
of computational problems) with Eric Blais.
- Lecture 24: Did you enjoy the course? Then consider taking
CS 462, which revisits some of the same topics, but at a much
deeper level.