# HG changeset patch # User Christian Urban # Date 1759507621 -3600 # Node ID e719e420cbc7d4b175f2804d1c1cbfd48cc51709 # Parent 69eddde11a65b64face3d215882093a63cddd914 updated diff -r 69eddde11a65 -r e719e420cbc7 handouts/ho02.pdf Binary file handouts/ho02.pdf has changed diff -r 69eddde11a65 -r e719e420cbc7 handouts/ho02.tex --- a/handouts/ho02.tex Fri Oct 03 10:10:33 2025 +0100 +++ b/handouts/ho02.tex Fri Oct 03 17:07:01 2025 +0100 @@ -258,7 +258,7 @@ \begin{equation} (r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO) -\label{big} +\label{bbbig} \end{equation} \noindent If we can find an equivalent regular expression that is @@ -268,7 +268,7 @@ $L(r)$ or in $L(r')$ does not matter as long as $r\equiv r'$. Yes? \footnote{You have checked this for yourself? Your friendly lecturer might talk rubbish\ldots{}one never knows.} In the example above you will see that the regular expression in -\eqref{big} is equivalent to just $r_1$. You can verify this by +\eqref{bbbig} is equivalent to just $r_1$. You can verify this by iteratively applying the simplification rules from above: \begin{center} @@ -624,7 +624,7 @@ $r^{\{n\}}$. In Scala we would introduce a constructor like \begin{center} -\code{case class NTIMES(r: Rexp, n: Int) extends Rexp} +\code{case NTIMES(r: Rexp, n: Int)} \end{center} \noindent With this fix we have a constant ``size'' regular expression diff -r 69eddde11a65 -r e719e420cbc7 progs/matcher/re2.sc --- a/progs/matcher/re2.sc Fri Oct 03 10:10:33 2025 +0100 +++ b/progs/matcher/re2.sc Fri Oct 03 17:07:01 2025 +0100 @@ -12,15 +12,17 @@ // // amm re2.sc all - -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 NTIMES(r: Rexp, n: Int) extends Rexp //explicit constructor for n-times +// regular expressions (as enum in Scala 3) +enum Rexp { + case ZERO // matches nothing + case ONE // matches an empty string + case CHAR(c: Char) // matches a character c + case ALT(r1: Rexp, r2: Rexp) // alternative + case SEQ(r1: Rexp, r2: Rexp) // sequence + case STAR(r: Rexp) // star + case NTIMES(r: Rexp, n: Int) // explicit n-times +} +import Rexp._ def nullable (r: Rexp) : Boolean = r match { @@ -145,8 +147,6 @@ size(ders(("a" * 20).toList, EVIL2)) // 7340068 - -@arg(doc = "All tests.") @main def all() = { test1(); test2() } diff -r 69eddde11a65 -r e719e420cbc7 progs/matcher/re3.sc --- a/progs/matcher/re3.sc Fri Oct 03 10:10:33 2025 +0100 +++ b/progs/matcher/re3.sc Fri Oct 03 17:07:01 2025 +0100 @@ -12,15 +12,18 @@ // // amm re3.sc all +// regular expressions (as enum in Scala 3) +enum Rexp { + case ZERO // matches nothing + case ONE // matches an empty string + case CHAR(c: Char) // matches a character c + case ALT(r1: Rexp, r2: Rexp) // alternative + case SEQ(r1: Rexp, r2: Rexp) // sequence + case STAR(r: Rexp) // star + case NTIMES(r: Rexp, n: Int) // explicit n-times +} +import Rexp._ -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 NTIMES(r: Rexp, n: Int) extends Rexp // the nullable function: tests whether the regular diff -r 69eddde11a65 -r e719e420cbc7 slides/slides01.pdf Binary file slides/slides01.pdf has changed diff -r 69eddde11a65 -r e719e420cbc7 slides/slides01.tex --- a/slides/slides01.tex Fri Oct 03 10:10:33 2025 +0100 +++ b/slides/slides01.tex Fri Oct 03 17:07:01 2025 +0100 @@ -244,11 +244,7 @@ \LARGE Formal Languages\\[-3mm] \end{tabular}} - %\begin{center} - %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm} - %\includegraphics[scale=0.31]{pics/ante2.jpg}\\ - %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)} - %\end{center} + \normalsize \begin{center} @@ -277,6 +273,11 @@ \end{tikzpicture} \end{center} + + \begin{textblock}{5}(12,3) + \includegraphics[scale=0.35]{qr01}\\ + \small Wifi: IET-Guest + \end{textblock} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -2058,12 +2059,24 @@ \begin{tabular}{lll} SGT TAs: & Flavio Melinte Citea\\ & Zoltan Meszaros\bigskip\\ -Amm Helpers & Flavio Melinte Citea & (flavio.melinte\_citea@kcl.ac.uk)\\ - & Zishan Rahman & (zishan.rahman@kcl.ac.uk)\medskip\\ +Amm + Github & Flavio Melinte Citea & (flavio.melinte\_citea@kcl.ac.uk)\\ +Helpers & Zishan Rahman & (zishan.rahman@kcl.ac.uk)\medskip\\ \end{tabular} \mbox{} \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\begin{center} +\begin{tabular}{c} +\includegraphics[scale=0.024]{awards.jpeg}\\ +\small I try my best, but \ldots +\end{tabular} +\end{center} +\mbox{} +\end{frame} + \begin{frame}[c] \end{frame} @@ -2106,22 +2119,6 @@ \begin{frame}[c] \end{frame} - -\begin{frame}[c] -\begin{mybox3}{Coursework} - Do we need to provide instructions on running the coursework files - if we're using languages other than Scala? Thanks -\end{mybox3}\pause - -\begin{mybox2}{Zip-File for Coursework} - Please, please submit a zipfile that generates a subdirectory - \begin{center} - \texttt{NameFamilyName} - \end{center} -\end{mybox2} -\end{frame} - - \begin{frame}[c] \begin{mybox3}{What is the trick?}\small What was the trick to improve the evil regular expressions matcher @@ -2132,6 +2129,20 @@ \end{mybox3} \end{frame} +\begin{frame}[c] +\begin{mybox3}{No Regex at Amazon AWS}\small +My friend who works at Amazon AWS told me they try to avoid +regexes whenever they can. So kind of echoes this joke from the week +1 handout. + +\begin{quote} +“Sometimes you have a programming problem and it seems like the +best solution is to use regular expressions; now you have two problems.” +\end{quote} + +\end{mybox3} +\end{frame} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{Thanks to Martin Mikusovic}