--- a/data.sty Mon Sep 30 10:47:49 2024 +0100
+++ b/data.sty Fri Oct 11 19:13:00 2024 +0100
@@ -558,3 +558,31 @@
17 29.51587
#18 73.14163
\end{filecontents}
+
+
+%
+% Example (abcdef){n} in Rust and Scala
+%
+
+\begin{filecontents}{re-rust2.data}
+ 0 0
+ 10000 2.655
+ 15000 6.146
+ 20000 11.268
+ 25000 18.251
+ 30000 27.739
+ 35000 38.441
+ 40000 51.953
+\end{filecontents}
+
+\begin{filecontents}{re-scala2.data}
+0 0.00019
+5000 0.01527
+10000 0.00634
+15000 0.00671
+20000 0.01144
+25000 0.00835
+30000 0.00885
+35000 0.02456
+40000 0.01786
+\end{filecontents}
\ No newline at end of file
--- a/handouts/ho03.tex Mon Sep 30 10:47:49 2024 +0100
+++ b/handouts/ho03.tex Fri Oct 11 19:13:00 2024 +0100
@@ -814,8 +814,8 @@
\end{lstlisting}}
\noindent
-It calculates a NFA from a regular expressions. At last we can run
-NFAs for the our evil regular expression examples. The graph on the
+It calculates a NFA from a regular expression. At last we can run
+NFAs for our evil regular expression examples. The graph on the
left shows that when translating a regular expression such as
$a^{?\{n\}} \cdot a^{\{n\}}$ into a NFA, the size can blow up and then
even the relative fast (on small examples) breadth-first search can be
Binary file hws/hw01.pdf has changed
--- a/hws/hw01.tex Mon Sep 30 10:47:49 2024 +0100
+++ b/hws/hw01.tex Fri Oct 11 19:13:00 2024 +0100
@@ -121,7 +121,26 @@
$[b]$.
\solution{for example $r^* = 1 + r \cdot r^*$ for any regular expression $r$.
- Can students think about why this is the case? - this would need a proof.}
+ Can students think about why this is the case? - this would need a proof.\bigskip
+
+
+ Lemma to prove: $A^* = \{[]\} \cup A \times A^*$ for any language $A$.\bigskip
+
+ The definition of ${}^*$: $\bigcup n. A^n$\bigskip
+
+ We first show $\subseteq$ of the lemma: a string $s \in A^*$, must also be in
+ $\bigcup n. A^n$, which means there is an $n$ such that $s\in A^n$.
+ If $n = 0$ then $s = []$ and $s$ is also in $\{[]\} \cup A \times A^*$.
+ If $n$ is bigger than $0$, then $s\in A^n$, which means by
+ definition of power that $s\in A \times A^{n - 1}$. But then
+ also $s \in A \times A^*$. That is one direction.\bigskip
+
+ The other direction: Two cases: (i) $s\in \{[]\}$ then
+ also $s\in A^*$. (ii) $s\in A \times A^*$ means there exists
+ an $n$ such that $s\in A\times A^n$. This in turn means
+ $s\in A^{n + 1}$ (by definition of power). But this also means $s\in A^*$.
+ So $\{[]\} \cup A \times A^*$ is a subset of $A^*$. Done!
+ }
\item What is meant by the notions \emph{evil regular expressions}
and by \emph{catastrophic backtracking}?
Binary file hws/hw02.pdf has changed
--- a/hws/hw02.tex Mon Sep 30 10:47:49 2024 +0100
+++ b/hws/hw02.tex Fri Oct 11 19:13:00 2024 +0100
@@ -14,7 +14,12 @@
\solution{Basic regular expressions are $\ZERO$, $\ONE$, $c$, $r_1 + r_2$,
$r_1 \cdot r_2$, $r^*$. The extended ones are the bounded
- repetitions, not, etc.}
+ repetitions, not, etc.
+
+
+ Maybe explain here how the extended regular expressions
+ are defined in terms of the basic ones.
+ }
\item What is the language recognised by the regular
expressions $(\ZERO^*)^*$.
Binary file hws/hw03.pdf has changed
Binary file hws/hw04.pdf has changed
Binary file hws/hw05.pdf has changed
Binary file hws/hw06.pdf has changed
Binary file hws/hw07.pdf has changed
Binary file hws/hw08.pdf has changed
Binary file hws/hw09.pdf has changed
--- a/progs/automata/thompson.sc Mon Sep 30 10:47:49 2024 +0100
+++ b/progs/automata/thompson.sc Fri Oct 11 19:13:00 2024 +0100
@@ -150,11 +150,11 @@
println("Breadth-first search EVIL1 / EVIL2")
for (i <- 1 to 13) {
- println(i + ": " + "%.5f".format(time_needed(2, tmatches_nfa(EVIL1(i), "a" * i))))
+ println(s"$i: ${"%.5f".format(time_needed(2, tmatches_nfa(EVIL1(i), "a" * i)))}")
}
for (i <- 1 to 100 by 5) {
- println(i + " " + "%.5f".format(time_needed(2, tmatches_nfa(EVIL2, "a" * i))))
+ println(s"$i: ${"%.5f".format(time_needed(2, tmatches_nfa(EVIL2, "a" * i)))}")
}
@@ -163,11 +163,11 @@
println("Depth-first search EVIL1 / EVIL2")
for (i <- 1 to 9) {
- println(i + " " + "%.5f".format(time_needed(2, tmatches_nfa2(EVIL1(i), "a" * i))))
+ println(s"$i: ${"%.5f".format(time_needed(2, tmatches_nfa2(EVIL1(i), "a" * i)))}")
}
for (i <- 1 to 7) {
- println(i + " " + "%.5f".format(time_needed(2, tmatches_nfa2(EVIL2, "a" * i))))
+ println(s"$i: ${"%.5f".format(time_needed(2, tmatches_nfa2(EVIL2, "a" * i)))}")
}
@@ -179,11 +179,11 @@
// the state explosion in the subset construction
for (i <- 1 to 7) {
- println(i + ": " + "%.5f".format(time_needed(2, tmatches_dfa(EVIL1(i), "a" * i))))
+ println(s"$i: ${"%.5f".format(time_needed(2, tmatches_dfa(EVIL1(i), "a" * i)))}")
}
for (i <- 1 to 100 by 5) {
- println(i + " " + "%.5f".format(time_needed(2, tmatches_dfa(EVIL2, "a" * i))))
+ println(s"$i: ${"%.5f".format(time_needed(2, tmatches_dfa(EVIL2, "a" * i)))}")
}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/matcher/cw1.sc Fri Oct 11 19:13:00 2024 +0100
@@ -0,0 +1,185 @@
+// Christian's Solution for CW 1
+import scala.language.implicitConversions
+
+// basic regular expressions
+abstract class Rexp
+case object ZERO extends Rexp
+case object ONE extends Rexp
+case class CHAR(c: Char) extends Rexp
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp
+case class STAR(r: Rexp) extends Rexp
+
+// extended regular expressions
+case class RANGE(cs: Set[Char]) extends Rexp // set of characters
+case class PLUS(r: Rexp) extends Rexp // plus
+case class OPTIONAL(r: Rexp) extends Rexp // optional
+case class INTER(r1: Rexp, r2: Rexp) extends Rexp // intersection
+case class NTIMES(r: Rexp, n: Int) extends Rexp // n-times
+case class UPTO(r: Rexp, n: Int) extends Rexp // up n-times
+case class FROM(r: Rexp, n: Int) extends Rexp // from n-times
+case class BETWEEN(r: Rexp, n: Int, m: Int) extends Rexp // between nm-times
+case class NOT(r: Rexp) extends Rexp // not
+
+// general version of CHAR, RANGE and ALL
+case class CFUN(f: Char => Boolean) extends Rexp // subsuming CHAR and RANGE
+
+def FCHAR(c: Char) = CFUN(c == _)
+val FALL = CFUN(_ => true)
+def FRANGE(cs: Set[Char]) = CFUN(cs.contains(_))
+
+// the nullable function: tests whether the regular
+// expression can recognise the empty string
+def nullable (r: Rexp) : Boolean = r match {
+ case ZERO => false
+ case ONE => true
+ case CHAR(_) => false
+ case ALT(r1, r2) => nullable(r1) || nullable(r2)
+ case SEQ(r1, r2) => nullable(r1) && nullable(r2)
+ case STAR(_) => true
+ case RANGE(_) => false
+ case PLUS(r) => nullable(r)
+ case OPTIONAL(_) => true
+ case INTER(r1, r2) => nullable(r1) && nullable(r2)
+ case NTIMES(r, n) => if (n == 0) true else nullable(r)
+ case UPTO(_, _) => true
+ case FROM(r, n) => if (n == 0) true else nullable(r)
+ case BETWEEN(r, n, m) => if (n == 0) true else nullable(r)
+ case NOT(r) => !nullable(r)
+ case CFUN(_) => false
+}
+
+// the derivative of a regular expression w.r.t. a character
+def der(c: Char, r: Rexp) : Rexp = r match {
+ case ZERO => ZERO
+ case ONE => ZERO
+ case CHAR(d) => if (c == d) ONE else ZERO
+ case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
+ case SEQ(r1, r2) =>
+ if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
+ else SEQ(der(c, r1), r2)
+ case STAR(r1) => SEQ(der(c, r1), STAR(r1))
+ case RANGE(cs) => if (cs contains c) ONE else ZERO
+ case PLUS(r) => SEQ(der(c, r), STAR(r))
+ case OPTIONAL(r) => der(c, r)
+ case INTER(r1, r2) => INTER(der(c, r1), der(c, r2))
+ case NTIMES(r, n) =>
+ if (n == 0) ZERO else SEQ(der(c, r), NTIMES(r, n - 1))
+ case UPTO(r, n) =>
+ if (n == 0) ZERO else SEQ(der(c, r), UPTO(r, n - 1))
+ case FROM(r, n) =>
+ if (n == 0) SEQ(der(c, r), STAR(r)) else SEQ(der(c, r), FROM(r, n - 1))
+ case BETWEEN(r, n, m) =>
+ if (m < n) ZERO else
+ if (n == 0 && m == 0) ZERO else
+ if (n == 0) SEQ(der(c, r), UPTO(r, m - 1))
+ else SEQ(der(c, r), BETWEEN(r, n - 1, m - 1))
+ case NOT(r) => NOT(der (c, r))
+ case CFUN(f) => if (f(c)) ONE else ZERO
+}
+
+// simplification
+def simp(r: Rexp) : Rexp = r match {
+ case ALT(r1, r2) => (simp(r1), simp(r2)) match {
+ case (ZERO, r2s) => r2s
+ case (r1s, ZERO) => r1s
+ case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s)
+ }
+ case SEQ(r1, r2) => (simp(r1), simp(r2)) match {
+ case (ZERO, _) => ZERO
+ case (_, ZERO) => ZERO
+ case (ONE, r2s) => r2s
+ case (r1s, ONE) => r1s
+ case (r1s, r2s) => SEQ(r1s, r2s)
+ }
+ case r => r
+}
+
+// the derivative w.r.t. a string (iterates der)
+def ders(s: List[Char], r: Rexp) : Rexp = s match {
+ case Nil => r
+ case c::s => ders(s, simp(der(c, r)))
+}
+
+// the main matcher function
+def matcher(r: Rexp, s: String) : Boolean =
+ nullable(ders(s.toList, r))
+
+
+// Test Cases
+//============
+
+// some syntactic convenience
+
+def charlist2rexp(s: List[Char]) : Rexp = s match {
+ case Nil => ONE
+ case c::Nil => CHAR(c)
+ case c::s => SEQ(CHAR(c), charlist2rexp(s))
+}
+
+given Conversion[String, Rexp] = (s => charlist2rexp(s.toList))
+
+extension (r: Rexp) {
+ def ~ (s: Rexp) = SEQ(r, s)
+ def % = STAR(r)
+}
+
+
+println("EMAIL:")
+val LOWERCASE = ('a' to 'z').toSet
+val DIGITS = ('0' to '9').toSet
+val SYMBOLS1 = ("_.-").toSet
+val SYMBOLS2 = (".-").toSet
+val EMAIL = { PLUS(CFUN(LOWERCASE | DIGITS | SYMBOLS1)) ~ "@" ~
+ PLUS(CFUN(LOWERCASE | DIGITS | SYMBOLS2)) ~ "." ~
+ BETWEEN(CFUN(LOWERCASE | Set('.')), 2, 6) }
+
+val my_email = "christian.urban@kcl.ac.uk"
+
+println(EMAIL);
+println(matcher(EMAIL, my_email))
+println(ders(my_email.toList,EMAIL))
+
+val ALL = CFUN((c:Char) => true)
+val COMMENT = "/*" ~ (NOT(ALL.% ~ "*/" ~ ALL.%)) ~ " * /"
+
+println(matcher(COMMENT, "/**/"))
+println(matcher(COMMENT, "/*foobar*/"))
+println(matcher(COMMENT, "/*test*/test*/"))
+println(matcher(COMMENT, "/*test/*test*/"))
+
+
+println("\n\nTEST TEST\n")
+
+val r1 = PLUS(PLUS(SEQ(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))))
+val r2 = PLUS(PLUS(SEQ(BETWEEN(CHAR('a'), 19, 19), OPTIONAL(CHAR('a')))))
+val s1 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+val s2 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+val s3 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+for (s <- List(s1,s2,s3)) {
+ println(matcher(r1, s))
+ println(matcher(r2, s))
+}
+
+
+// for measuring time
+def time_needed[T](i: Int, code: => T) = {
+ val start = System.nanoTime()
+ for (j <- 1 to i) code
+ val end = System.nanoTime()
+ (end - start) / (i * 1.0e9)
+}
+
+
+//@main
+def test(file: String) = {
+ println("Test a{n}")
+
+ for (i <- 0 to 200000 by 5000) {
+ val re = NTIMES(SEQ(SEQ(CHAR('a'), CHAR('b')), CHAR('c')), i)
+
+ print(f"$i: ${time_needed(2, matcher(re, "abc" * i))}%.5f")
+ println(s" ${matcher(re, "abcd" * i)}")
+ }
+}
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/matcher/cw1template.sc Fri Oct 11 19:13:00 2024 +0100
@@ -0,0 +1,80 @@
+// A template of the simple matcher with simplification
+// of derivatives to be used in CW1
+
+
+abstract class Rexp
+case object ZERO extends Rexp
+case object ONE extends Rexp
+case class CHAR(c: Char) extends Rexp
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp
+case class STAR(r: Rexp) extends Rexp
+
+case class RANGE(cs: Set[Char]) extends Rexp // set of characters
+case class PLUS(r: Rexp) extends Rexp // plus
+case class OPTIONAL(r: Rexp) extends Rexp // optional
+case class INTER(r1: Rexp, r2: Rexp) extends Rexp // intersection
+case class NTIMES(r: Rexp, n: Int) extends Rexp // n-times
+case class UPTO(r: Rexp, n: Int) extends Rexp // up n-times
+case class FROM(r: Rexp, n: Int) extends Rexp // from n-times
+case class BETWEEN(r: Rexp, n: Int, m: Int) extends Rexp // between nm-times
+case class NOT(r: Rexp) extends Rexp // not
+case class CFUN(f: Char => Boolean) extends Rexp
+
+
+
+// the nullable function: tests whether the regular
+// expression can recognise the empty string
+def nullable (r: Rexp) : Boolean = r match {
+ case ZERO => false
+ case ONE => true
+ case CHAR(_) => false
+ case ALT(r1, r2) => nullable(r1) || nullable(r2)
+ case SEQ(r1, r2) => nullable(r1) && nullable(r2)
+ case STAR(_) => true
+ case NTIMES(r, i) => if (i == 0) true else nullable(r)
+ // ??? other cases
+}
+
+// the derivative of a regular expression w.r.t. a character
+def der(c: Char, r: Rexp) : Rexp = r match {
+ case ZERO => ZERO
+ case ONE => ZERO
+ case CHAR(d) => if (c == d) ONE else ZERO
+ case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
+ case SEQ(r1, r2) =>
+ if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
+ else SEQ(der(c, r1), r2)
+ case STAR(r1) => SEQ(der(c, r1), STAR(r1))
+ case NTIMES(r, i) =>
+ if (i == 0) ZERO else SEQ(der(c, r), NTIMES(r, i - 1))
+ // ??? other cases
+}
+
+// simplification
+def simp(r: Rexp) : Rexp = r match {
+ case ALT(r1, r2) => (simp(r1), simp(r2)) match {
+ case (ZERO, r2s) => r2s
+ case (r1s, ZERO) => r1s
+ case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s)
+ }
+ case SEQ(r1, r2) => (simp(r1), simp(r2)) match {
+ case (ZERO, _) => ZERO
+ case (_, ZERO) => ZERO
+ case (ONE, r2s) => r2s
+ case (r1s, ONE) => r1s
+ case (r1s, r2s) => SEQ(r1s, r2s)
+ }
+ case r => r
+}
+
+// the derivative w.r.t. a string (iterates der and simp)
+def ders(s: List[Char], r: Rexp) : Rexp = s match {
+ case Nil => r
+ case c::s => ders(s, simp(der(c, r)))
+}
+
+// the main matcher function
+def matcher(r: Rexp, s: String) : Boolean =
+ nullable(ders(s.toList, r))
+
--- a/progs/matcher/re3.sc Mon Sep 30 10:47:49 2024 +0100
+++ b/progs/matcher/re3.sc Fri Oct 11 19:13:00 2024 +0100
@@ -184,8 +184,19 @@
}
}
+@main
+def test5() = {
+ println("Test (abcdef){n}")
+ val re = SEQ(CHAR('a'), SEQ(CHAR('b'), SEQ(CHAR('c'), SEQ(CHAR('d'), SEQ(CHAR('e'), CHAR('f'))))))
+
+ for (i <- 0 to 40000 by 5000) {
+ println(f"$i: ${time_needed(1, matcher(NTIMES(re, i), "abcdef" * i))}%.5f")
+ }
+}
+
+
@arg(doc = "Tests that show not all is hunky-dory, but a solution leads too far afield.")
@main
-def fail() = { test3(); test4() }
+def fail() = { test3(); test4(); test5() }
--- a/slides/compiled.data Mon Sep 30 10:47:49 2024 +0100
+++ b/slides/compiled.data Fri Oct 11 19:13:00 2024 +0100
@@ -1,6 +1,6 @@
%% LaTeX2e file `compiled.data'
%% generated by the `filecontents' environment
-%% from source `slides02' on 2016/10/04.
+%% from source `slides03' on 2024/10/10.
%%
%1 0.234146
%5000 0.227539
--- a/slides/compiled2.data Mon Sep 30 10:47:49 2024 +0100
+++ b/slides/compiled2.data Fri Oct 11 19:13:00 2024 +0100
@@ -1,6 +1,6 @@
%% LaTeX2e file `compiled2.data'
%% generated by the `filecontents' environment
-%% from source `slides02' on 2016/10/04.
+%% from source `slides03' on 2024/10/10.
%%
0 0
200 0.222058
--- a/slides/interpreted.data Mon Sep 30 10:47:49 2024 +0100
+++ b/slides/interpreted.data Fri Oct 11 19:13:00 2024 +0100
@@ -1,6 +1,6 @@
%% LaTeX2e file `interpreted.data'
%% generated by the `filecontents' environment
-%% from source `slides02' on 2016/10/04.
+%% from source `slides03' on 2024/10/10.
%%
200 1.005863
400 7.8296765
--- a/slides/interpreted2.data Mon Sep 30 10:47:49 2024 +0100
+++ b/slides/interpreted2.data Fri Oct 11 19:13:00 2024 +0100
@@ -1,6 +1,6 @@
%% LaTeX2e file `interpreted2.data'
%% generated by the `filecontents' environment
-%% from source `slides02' on 2016/10/04.
+%% from source `slides03' on 2024/10/10.
%%
0 0
200 1.005863
Binary file slides/slides01.pdf has changed
Binary file slides/slides02.pdf has changed
--- a/slides/slides02.tex Mon Sep 30 10:47:49 2024 +0100
+++ b/slides/slides02.tex Fri Oct 11 19:13:00 2024 +0100
@@ -43,7 +43,7 @@
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
- Office Hour: & Thurdays 15 -- 16\\
+ Office Hour: & Friday 12 -- 14\\
Location: & N7.07 (North Wing, Bush House)\\
Slides \& Progs: & KEATS\\
Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\
@@ -69,11 +69,16 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-{
-\setbeamercolor{background canvas}{bg=cream}
-\begin{frame}<1-4>[c]
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{mybox3}{From Pollev last week}\it
+Will C++ users be publicly shamed and humiliated in front of the class?
+\end{mybox3}
+
\end{frame}
-}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
@@ -83,10 +88,12 @@
\footnotesize
\begin{center}
- {\normalsize Graphs: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$} and strings \bl{$\underbrace{\,a\ldots a\,}_{n}$}}\medskip\\
+ {\normalsize Graphs: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$} and strings \bl{$\underbrace{\,a\ldots a\,}_{n}$}}\\[-2mm]
\begin{tabular}{@{}cc@{}}
\begin{tikzpicture}
\begin{axis}[
+ title={Graph: $\texttt{(a*)*\,b}$ and strings
+ $\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
xlabel={$n$},
x label style={at={(1.05,0.0)}},
ylabel={time in secs},
@@ -97,13 +104,15 @@
ytick={0,5,...,30},
scaled ticks=false,
axis lines=left,
- width=5cm,
+ width=5.5cm,
height=4.5cm,
- legend entries={Python,Ruby},
+ legend entries={Python, Java 8, JavaScript, Swift},
legend pos=north west,
legend cell align=left]
-\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
-\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data};
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
+\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
\end{axis}
\end{tikzpicture}
&
@@ -132,12 +141,21 @@
\end{center}
\small
-In the handouts is a similar graph for \bl{$(a^*)^* \cdot b$} and Java 8,
-JavaScript and Python.
-
+\begin{textblock}{14}(1,14.6)
+In the handouts is a similar graph for \bl{$(a^*)^* \cdot b$} and Java,
+JavaScript, Python and more.
+\end{textblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+{
+\setbeamercolor{background canvas}{bg=cream}
+\begin{frame}<1-4>[c]
+\end{frame}
+}
+
+
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Evil Regular Expressions}
Binary file slides/slides03.pdf has changed
--- a/slides/slides03.tex Mon Sep 30 10:47:49 2024 +0100
+++ b/slides/slides03.tex Fri Oct 11 19:13:00 2024 +0100
@@ -34,8 +34,8 @@
\normalsize
\begin{center}
\begin{tabular}{ll}
- Email: & christian.urban at kcl.ac.uk\\
-Office Hour: & Thurdays 15 -- 16\\
+ Email: & christian.urban at kcl.ac.uk\\
+ Office Hour: & Friday 12 -- 14\\
Location: & N7.07 (North Wing, Bush House)\\
Slides \& Progs: & KEATS\\
Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\
@@ -61,6 +61,94 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+{
+\setbeamercolor{background canvas}{bg=cream}
+\begin{frame}[c]
+\frametitle{For Installation Problems}
+
+\begin{itemize}
+\item Harry Dilnot (harry.dilnot@kcl.ac.uk) \\
+ \;\;Windows expert
+\item Oliver Iliffe (oliver.iliffe@kcl.ac.uk)
+\end{itemize}
+
+\end{frame}
+}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{mybox3}{From Pollev last week}\it
+Is the equivalence of two regexes belong in the P or NP class of problems?
+\end{mybox3}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{mybox3}{From Pollev last week}\it
+ If state machines are not efficient, then how/why do many lexer
+ packages like the logos crate in rust compile down a lexer
+ definition down to a jump table driven state machine?
+ \textcolor{gray}{Could we
+ achieve quicker lexing with things like SIMD instructions?}
+\end{mybox3}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\boldmath$(abcdef)^{\{n\}}$ in Rust and Scala}
+
+\begin{textblock}{14}(1,3)
+\begin{tikzpicture}
+\begin{axis}[
+ xlabel={copies of $[abcdef]$},
+ x label style={at={(0.45,-0.16)}},
+ ylabel={time in secs},
+ enlargelimits=false,
+ ytick={0,10,...,60},
+ ymax=65,
+ xmax=50000,
+ xtick={0,10000,...,40000},
+ scaled ticks=false,
+ axis lines=left,
+ width=10cm,
+ height=6cm,
+ legend entries={Rust, Scala V3},
+ legend style={font=\small,at={(1.15,0.48)},anchor=north},
+ legend cell align=left]
+ \addplot[blue,mark=*, mark options={fill=white}] table {re-rust2.data};
+ \only<2>{\addplot[red,mark=*, mark options={fill=white}] table {re-scala2.data};}
+\end{axis}
+\end{tikzpicture}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{mybox3}{From Pollev last week}\it
+ For a regular expression $r = r_1 \cdot r_2$, to prove that
+ $der\;c\;r = (der\;c\;r) \cdot r^{\{n-1\}}$, is there a
+ way to prove it in the general case instead
+ of how you do the calculations for each $n$ in the videos?
+\end{mybox3}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
{
\setbeamercolor{background canvas}{bg=cream}
\begin{frame}<1-10>[c]
@@ -1670,7 +1758,9 @@
% \end{center}
% \end{frame}
-% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
@@ -1760,6 +1850,8 @@
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
\begin{frame}<1-3>[c]
\end{frame}
@@ -1795,40 +1887,108 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\mbox{CW1: Regexes and \boldmath$L$-function}}
+
+Given
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{20mm}}l@ {\hspace{2mm}}l@ {\hspace{2mm}}l}
+\bl{$r^+$} & \bl{$L(r^+)$} & \bl{$\dn$} & \bl{$\bigcup_{1\le i}.\;L(r)^i$}\\
+\bl{$r^?$} & \bl{$L(r^?)$} & \bl{$\dn$} & \bl{$L(r) \cup \{[]\}$}\\
+\bl{$r_1 \,\&\, r_2$} & \bl{$L(r_1 \& r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cap L(r_2)$} \\
+\bl{$r^{\{n\}}$} & \bl{$L(r^{\{n\}})$} & \bl{$\dn$} & \bl{$L(r)^n$}\\
+\bl{$r^{\{..m\}}$} & \bl{$L(r^{\{..m\}})$} & \bl{$\dn$} & \bl{$\bigcup_{0\le i \le m}.\;L(r)^i$}\\
+\bl{$r^{\{n..\}}$} & \bl{$L(r^{\{n..\}})$} & \bl{$\dn$} & \bl{$\bigcup_{n\le i}.\;L(r)^i$}\\
+\bl{$r^{\{n..m\}}$} & \bl{$L(r^{\{n..m\}})$} & \bl{$\dn$} & \bl{$\bigcup_{n\le i \le m}.\;L(r)^i$}\\
+\bl{$\sim{}r$} & \bl{$L(\sim{}r)$} & \bl{$\dn$} & \bl{$\Sigma^* - L(r)$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Nullable}
+
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+\bl{$nullable(r^+)$} & \bl{$\dn$} & \bl{$nullable(r)$}\\
+\bl{$nullable(r^?)$} & \bl{$\dn$} & \bl{\textit{true}}\\
+\bl{$nullable(r_1 \,\&\, r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \wedge nullable(r_2)$}\\
+\bl{$nullable(r^{\{n\}})$} & \bl{$\dn$} & \bl{\textit{if} $n = 0$ \textit{then} \textit{true} \textit{else} $nullable(r)$} \\
+\bl{$nullable(r^{\{..m\}})$} & \bl{$\dn$} & \bl{\textit{true}} \\
+\bl{$nullable (r^{\{n..\}})$} & \bl{$\dn$} & \bl{\textit{if} $n = 0$ \textit{then} \textit{true} \textit{else} $nullable(r)$}\\
+\bl{$nullable (r^{\{n..m\}})$} & \bl{$\dn$} & \bl{\textit{if} $n = 0$ \textit{then} \textit{true} \textit{else} $nullable(r)$}\\
+\bl{$nullable (\sim{}r)$} & \bl{$\dn$} & \bl{$!\,nullable(r)$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Derivative}
+
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+\bl{$der\,c\,(r^+)$} & \bl{$\dn$} & \bl{$(der\,c\,r)\cdot r^*$}\\
+\bl{$der\,c\,(r^?)$} & \bl{$\dn$} & \bl{$der\,c\,r$}\\
+\bl{$der\,c\,(r_1 \,\&\, r_2)$} & \bl{$\dn$} & \bl{$(der\,c\,r_1) \;\&\; (der\,c\,r_2)$}\\
+\bl{$der\,c\,(r^{\{n\}})$} & \bl{$\dn$} & \bl{\textit{if} $n = 0$ \textit{then} $\ZERO$ \textit{else} $(der\,c\,r)\cdot r^{\{n - 1\}}$} \\
+\bl{$der\,c\,(r^{\{..m\}})$} & \bl{$\dn$} & \bl{\textit{if} $m = 0$ \textit{then} $\ZERO$ \textit{else} $(der\,c\,r)\cdot r^{\{..m - 1\}}$}\\
+\bl{$der\,c\,(r^{\{n..\}})$} & \bl{$\dn$} & \bl{\textit{if} $n = 0$ \textit{then} $(der\,c\,r)\cdot r^*$ \textit{else} $(der\,c\,r)\cdot r^{\{n - 1..\}}$}\\
+ \bl{$der\,c\,(r^{\{n..m\}})$} & \bl{$\dn$} & \bl{\textit{if} $n = 0 \wedge m = 0$ \textit{then} $\ZERO$ \textit{else}}\\
+ & & \bl{\textit{if} $ n = 0$ \textit{then} $(der\,c\,r)\cdot r^{\{..m-1\}}$
+ \textit{else} $(der\,c\,r)\cdot r^{\{n-1..m-1\}}$}\\
+\bl{$der\,c\,(\sim{}r)$} & \bl{$\dn$} & \bl{$\sim\,(der\,c\,r)$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
\begin{frame}<1-15>[c]
\end{frame}
-\begin{frame}[t]
-\begin{mybox3}{}
- I always thought dfa's needed a transition for each state for each
- character, and if not it would be an nfa not a dfa. Is there an
- example that disproves this?
-\end{mybox3}
-\end{frame}
+% \begin{frame}[t]
+% \begin{mybox3}{}
+% I always thought dfa's needed a transition for each state for each
+% character, and if not it would be an nfa not a dfa. Is there an
+% example that disproves this?
+% \end{mybox3}
+% \end{frame}
-\begin{frame}<1-12>[c]
-\end{frame}
+% \begin{frame}<1-12>[c]
+% \end{frame}
-\begin{frame}[t]
-\begin{mybox3}{}
- Do the regular expression matchers in Python and Java 8 have more
- features than the one implemented in this module? Or is there
- another reason for their inefficiency?
-\end{mybox3}
-\end{frame}
+% \begin{frame}[t]
+% \begin{mybox3}{}
+% Do the regular expression matchers in Python and Java 8 have more
+% features than the one implemented in this module? Or is there
+% another reason for their inefficiency?
+% \end{mybox3}
+% \end{frame}
-\begin{frame}[c]
- \begin{itemize}
- \item CW / censored some msgs
- \item power law / proof
- \item CW feedback
- \item too polished CW submissions
- \item no open book
- \end{itemize}
-\end{frame}
+% \begin{frame}[c]
+% \begin{itemize}
+% \item CW / censored some msgs
+% \item power law / proof
+% \item CW feedback
+% \item too polished CW submissions
+% \item no open book
+% \end{itemize}
+% \end{frame}
\end{document}
Binary file slides/slides04.pdf has changed
Binary file slides/slides05.pdf has changed
Binary file slides/slides06.pdf has changed
Binary file slides/slides07.pdf has changed
Binary file slides/slides08.pdf has changed
Binary file slides/slides09.pdf has changed
Binary file slides/slides10.pdf has changed