diff -r dc3c35673e94 -r dbf9d710ce65 handouts/ho01.tex --- a/handouts/ho01.tex Mon Aug 30 15:50:27 2021 +0100 +++ b/handouts/ho01.tex Tue Aug 31 11:49:09 2021 +0100 @@ -42,13 +42,13 @@ \begin{document} -\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018, 2019, 2020} +\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021} \section*{Handout 1} The purpose of a compiler is to transform a program a human can read and -write into code the machine can run as fast as possible. Developing a +write into code machines can run as fast as possible. Developing a compiler is an old craft going back to 1952 with the first compiler written by Grace Hopper.\footnote{Who many years ago was invited on a talk show hosted by David Letterman. @@ -344,7 +344,7 @@ \noindent Finally, on 2 July 2019 Cloudflare had a global outage because of a -regular expression (they had no outage for the last 6 years). What +regular expression (they had no outage for the 6 years before). What happened is nicely explained in the blog: \begin{center} @@ -531,7 +531,7 @@ If you prefer to think in terms of the implementation of regular expressions in Scala, the constructors and classes relate as follows\footnote{More about Scala is -in the handout about \emph{A Crash-Course on Scala}.} +in the handout about \emph{A Crash-Course on Scala} from PEP.} \begin{center} \begin{tabular}{rcl} @@ -621,6 +621,8 @@ & = & L(r_1 + (r_2 + r_3)) \end{eqnarray*} +\noindent +That means both languages are the same. The point of the definition of $L$ is that we can use it to precisely specify when a string $s$ is matched by a regular expression $r$, namely if and only if $s \in L(r)$. In fact we @@ -715,7 +717,7 @@ expressions and the notion of derivatives. Earlier versions of this theorem used always automata in the proof. Using this theorem we can show that regular languages are closed under -complementation, something which Gasarch in his +complementation, something which Bill Gasarch in his Computational Complexity blog\footnote{\url{http://goo.gl/2R11Fw}} assumed can only be shown via automata. So even somebody who has written a 700+-page book\footnote{\url{http://goo.gl/fD0eHx}} on regular