# HG changeset patch # User Christian Urban # Date 1728670380 -3600 # Node ID ce5de01b963272b0e787d9fadbd37bc9d662d9d9 # Parent 4189cb63e5db58fd4a1c69484c3980900907e212 updated diff -r 4189cb63e5db -r ce5de01b9632 data.sty --- 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 diff -r 4189cb63e5db -r ce5de01b9632 handouts/ho03.tex --- 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 diff -r 4189cb63e5db -r ce5de01b9632 hws/hw01.pdf Binary file hws/hw01.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 hws/hw01.tex --- 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}? diff -r 4189cb63e5db -r ce5de01b9632 hws/hw02.pdf Binary file hws/hw02.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 hws/hw02.tex --- 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^*)^*$. diff -r 4189cb63e5db -r ce5de01b9632 hws/hw03.pdf Binary file hws/hw03.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 hws/hw04.pdf Binary file hws/hw04.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 hws/hw05.pdf Binary file hws/hw05.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 hws/hw06.pdf Binary file hws/hw06.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 hws/hw07.pdf Binary file hws/hw07.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 hws/hw08.pdf Binary file hws/hw08.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 hws/hw09.pdf Binary file hws/hw09.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 progs/automata/thompson.sc --- 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)))}") } diff -r 4189cb63e5db -r ce5de01b9632 progs/matcher/cw1.sc --- /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)}") + } +} + diff -r 4189cb63e5db -r ce5de01b9632 progs/matcher/cw1template.sc --- /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)) + diff -r 4189cb63e5db -r ce5de01b9632 progs/matcher/re3.sc --- 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() } diff -r 4189cb63e5db -r ce5de01b9632 slides/compiled.data --- 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 diff -r 4189cb63e5db -r ce5de01b9632 slides/compiled2.data --- 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 diff -r 4189cb63e5db -r ce5de01b9632 slides/interpreted.data --- 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 diff -r 4189cb63e5db -r ce5de01b9632 slides/interpreted2.data --- 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 diff -r 4189cb63e5db -r ce5de01b9632 slides/slides01.pdf Binary file slides/slides01.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 slides/slides02.pdf Binary file slides/slides02.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 slides/slides02.tex --- 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} diff -r 4189cb63e5db -r ce5de01b9632 slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 slides/slides03.tex --- 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} diff -r 4189cb63e5db -r ce5de01b9632 slides/slides04.pdf Binary file slides/slides04.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 slides/slides05.pdf Binary file slides/slides05.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 slides/slides06.pdf Binary file slides/slides06.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 slides/slides07.pdf Binary file slides/slides07.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 slides/slides08.pdf Binary file slides/slides08.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 slides/slides09.pdf Binary file slides/slides09.pdf has changed diff -r 4189cb63e5db -r ce5de01b9632 slides/slides10.pdf Binary file slides/slides10.pdf has changed