diff -r c0600f8b6427 -r 5176cbb819c2 hws/hw01.tex --- a/hws/hw01.tex Thu Sep 19 15:47:33 2024 +0100 +++ b/hws/hw01.tex Thu Sep 19 16:32:26 2024 +0100 @@ -18,15 +18,20 @@ \url{http://www.scala-lang.org} \end{center} - and the Ammonite REPL from - - \begin{center} - \url{https://ammonite.io} - \end{center} + % and the Ammonite REPL from + % + % \begin{center} + % \url{https://ammonite.io} + % \end{center} If you want to follow the code I present during the - lectures, read the handout about Scala. Make sure Ammonite - uses the Scala 3 compiler. + lectures, it might be useful to install VS Code or Codium. + I will be using Scala Version 3.5, which has the \texttt{scala-cli} + REPL used in PEP already built in. + + %handout about Scala. + %Make sure Ammonite + %uses the Scala 3 compiler. %\item {\bf (Optional)} Have a look at the crawler programs. % Can you find a usage for them in your daily programming @@ -71,13 +76,15 @@ Is in general $A\,@\,B$ equal to $B\,@\,A$? \solution{ What is $A @ {[]}$? Are there special cases - where $A @ B = B @ A$? } + where $A @ B = B @ A$? Obviously when $A = B$ the stament is true. + But there are also cases when $A \not= B$, for example $A = \{a\}$ + and $B = \{aaa\}$.} \item Assume a set $A$ contains 4 strings and a set $B$ contains 7 strings. None of the strings is the empty string. How many strings are in $A \,@\, B$? - \solution{28, but there are corner cases where there are fewer + \solution{Everyone will probably answer with 28, but there are corner cases where there are fewer than 28 elements. Can students think of such corner cases? For example $A = \{a, ab, \ldots\}$, $B = \{bc, c,\ldots\}$ } @@ -100,7 +107,8 @@ allowed to contain stars? (4) How many if they are also not allowed to contain $\_ + \_$? - \solution{1-3 are infinite (tell the idea why - examples); 4 is five - remember regexes are trees.} + \solution{1-3 are infinite (tell the idea why and give examples); + 4 is five - remember regexes are trees (that is the main point of the question.} \item When are two regular expressions equivalent? Can you think of instances where two regular expressions match @@ -110,12 +118,17 @@ $[b]$. \solution{for example $r^* = 1 + r \cdot r^*$ for any regular expression $r$. - Can students think about why this is the case?} + Can students think about why this is the case? - this would need a proof.} \item What is meant by the notions \emph{evil regular expressions} and by \emph{catastrophic backtracking}? - \solution{catastrophic backtracking also applies to other regexes, not just $(a^*)^*b$} + \solution{catastrophic backtracking also applies to other regexes, + not just $(a^*)^*b$. Maybe + \url{https://www.trevorlasn.com/blog/when-regex-goes-wrong/} is + of help - even the CrowdStrike issue had an underlying problem + with a regex, though this one was not due to catastrophic + backtracking.} \item Given the regular expression $(a + b)^* \cdot b \cdot (a + b)^*$, which of the following regular expressions are equivalent