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