## CS 360: Introduction to the Theory of Computing -- Fall 2019

### Enrichment

• 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 L1 and L2 to automata for some function of L1 and L2, 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 G1 and G2, will decide if L(G1) = L(G2). 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 ≠ yk 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 = { (an bn)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.