16 |
16 |
17 \begin{center} |
17 \begin{center} |
18 \url{http://www.scala-lang.org} |
18 \url{http://www.scala-lang.org} |
19 \end{center} |
19 \end{center} |
20 |
20 |
21 and the Ammonite REPL from |
21 % and the Ammonite REPL from |
22 |
22 % |
23 \begin{center} |
23 % \begin{center} |
24 \url{https://ammonite.io} |
24 % \url{https://ammonite.io} |
25 \end{center} |
25 % \end{center} |
26 |
26 |
27 If you want to follow the code I present during the |
27 If you want to follow the code I present during the |
28 lectures, read the handout about Scala. Make sure Ammonite |
28 lectures, it might be useful to install VS Code or Codium. |
29 uses the Scala 3 compiler. |
29 I will be using Scala Version 3.5, which has the \texttt{scala-cli} |
|
30 REPL used in PEP already built in. |
|
31 |
|
32 %handout about Scala. |
|
33 %Make sure Ammonite |
|
34 %uses the Scala 3 compiler. |
30 |
35 |
31 %\item {\bf (Optional)} Have a look at the crawler programs. |
36 %\item {\bf (Optional)} Have a look at the crawler programs. |
32 % Can you find a usage for them in your daily programming |
37 % Can you find a usage for them in your daily programming |
33 % life? Can you improve them? For example in cases there |
38 % life? Can you improve them? For example in cases there |
34 % are links that appear on different recursion levels, the |
39 % are links that appear on different recursion levels, the |
69 is also written as $\_ \,@\, \_$. According to |
74 is also written as $\_ \,@\, \_$. According to |
70 this definition, what is $A \,@\, \{\}$ equal to? |
75 this definition, what is $A \,@\, \{\}$ equal to? |
71 Is in general $A\,@\,B$ equal to $B\,@\,A$? |
76 Is in general $A\,@\,B$ equal to $B\,@\,A$? |
72 |
77 |
73 \solution{ What is $A @ {[]}$? Are there special cases |
78 \solution{ What is $A @ {[]}$? Are there special cases |
74 where $A @ B = B @ A$? } |
79 where $A @ B = B @ A$? Obviously when $A = B$ the stament is true. |
|
80 But there are also cases when $A \not= B$, for example $A = \{a\}$ |
|
81 and $B = \{aaa\}$.} |
75 |
82 |
76 \item Assume a set $A$ contains 4 strings and a set $B$ |
83 \item Assume a set $A$ contains 4 strings and a set $B$ |
77 contains 7 strings. None of the strings is the empty |
84 contains 7 strings. None of the strings is the empty |
78 string. How many strings are in $A \,@\, B$? |
85 string. How many strings are in $A \,@\, B$? |
79 |
86 |
80 \solution{28, but there are corner cases where there are fewer |
87 \solution{Everyone will probably answer with 28, but there are corner cases where there are fewer |
81 than 28 elements. Can students think of such corner cases? |
88 than 28 elements. Can students think of such corner cases? |
82 For example $A = \{a, ab, \ldots\}$, $B = \{bc, c,\ldots\}$ } |
89 For example $A = \{a, ab, \ldots\}$, $B = \{bc, c,\ldots\}$ } |
83 |
90 |
84 \item How is the power of a language defined? (Hint: There are two |
91 \item How is the power of a language defined? (Hint: There are two |
85 rules, one for $\_^0$ and one for $\_^{n+1}$.) |
92 rules, one for $\_^0$ and one for $\_^{n+1}$.) |
98 \textbf{only} the string $abcd$? (2) How many if they cannot include |
105 \textbf{only} the string $abcd$? (2) How many if they cannot include |
99 $\ONE$ and $\ZERO$? (3) How many if they are also not |
106 $\ONE$ and $\ZERO$? (3) How many if they are also not |
100 allowed to contain stars? (4) How many if they are also |
107 allowed to contain stars? (4) How many if they are also |
101 not allowed to contain $\_ + \_$? |
108 not allowed to contain $\_ + \_$? |
102 |
109 |
103 \solution{1-3 are infinite (tell the idea why - examples); 4 is five - remember regexes are trees.} |
110 \solution{1-3 are infinite (tell the idea why and give examples); |
|
111 4 is five - remember regexes are trees (that is the main point of the question.} |
104 |
112 |
105 \item When are two regular expressions equivalent? Can you |
113 \item When are two regular expressions equivalent? Can you |
106 think of instances where two regular expressions match |
114 think of instances where two regular expressions match |
107 the same strings, but it is not so obvious that they do? |
115 the same strings, but it is not so obvious that they do? |
108 For example $a + b$ and $b + a$ do not count\ldots they |
116 For example $a + b$ and $b + a$ do not count\ldots they |
109 obviously match the same strings, namely $[a]$ and |
117 obviously match the same strings, namely $[a]$ and |
110 $[b]$. |
118 $[b]$. |
111 |
119 |
112 \solution{for example $r^* = 1 + r \cdot r^*$ for any regular expression $r$. |
120 \solution{for example $r^* = 1 + r \cdot r^*$ for any regular expression $r$. |
113 Can students think about why this is the case?} |
121 Can students think about why this is the case? - this would need a proof.} |
114 |
122 |
115 \item What is meant by the notions \emph{evil regular expressions} |
123 \item What is meant by the notions \emph{evil regular expressions} |
116 and by \emph{catastrophic backtracking}? |
124 and by \emph{catastrophic backtracking}? |
117 |
125 |
118 \solution{catastrophic backtracking also applies to other regexes, not just $(a^*)^*b$} |
126 \solution{catastrophic backtracking also applies to other regexes, |
|
127 not just $(a^*)^*b$. Maybe |
|
128 \url{https://www.trevorlasn.com/blog/when-regex-goes-wrong/} is |
|
129 of help - even the CrowdStrike issue had an underlying problem |
|
130 with a regex, though this one was not due to catastrophic |
|
131 backtracking.} |
119 |
132 |
120 \item Given the regular expression $(a + b)^* \cdot b \cdot (a + b)^*$, |
133 \item Given the regular expression $(a + b)^* \cdot b \cdot (a + b)^*$, |
121 which of the following regular expressions are equivalent |
134 which of the following regular expressions are equivalent |
122 |
135 |
123 \begin{center} |
136 \begin{center} |