--- a/progs/matcher/re3.sc	Thu Oct 15 09:22:33 2020 +0100
+++ b/progs/matcher/re3.sc	Sat Oct 17 13:14:19 2020 +0100
@@ -146,3 +146,31 @@
 def all() = { test1(); test2() } 
 
 
+
+
+
+// test: (a + aa)*
+val EVIL3 = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a'))))
+
+// test: (1 + a + aa)*
+val EVIL4 = STAR(ALT(ONE, ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))))
+
+@doc("Test Evil3")
+@main
+def test3() = {
+  println("Test (a + aa)*")
+
+  for (i <- 0 to 35 by 5) {
+    println(f"$i: ${time_needed(1, matcher(EVIL3, "a" * i))}%.5f")
+  }
+}
+
+@doc("Test Evil4")
+@main
+def test4() = {
+  println("Test (1 + a + aa)*")
+
+  for (i <- 0 to 35 by 5) {
+    println(f"$i: ${time_needed(1, matcher(EVIL4, "a" * i))}%.5f")
+  }
+}
\ No newline at end of file

Binary file slides/slides02.pdf has changed

--- a/slides/slides02.tex	Thu Oct 15 09:22:33 2020 +0100
+++ b/slides/slides02.tex	Sat Oct 17 13:14:19 2020 +0100
@@ -895,6 +895,8 @@
 \end{tikzpicture}
 \end{center}
 
+code by Archie Collard
+
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 

Binary file slides/slides03.pdf has changed

--- a/slides/slides03.tex	Thu Oct 15 09:22:33 2020 +0100
+++ b/slides/slides03.tex	Sat Oct 17 13:14:19 2020 +0100
@@ -736,12 +736,131 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Subset Construction}
+
+
+\begin{textblock}{5}(1,3.5)
+\begin{center}
+\begin{tikzpicture}[node distance=6mm,scale=0.7,>=stealth',very thick,
+                             every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
+\node[state,initial]  (Q_0)  {$\mbox{Q}_0$};
+\node[state] (Q_1) [below=of Q_0] {$\mbox{Q}_1$};
+\node[state, accepting] (Q_2) [below=of Q_1] {$\mbox{Q}_2$};
+
+\path[->] (Q_0) edge node [left]  {\alert{$1$}} (Q_1);
+\path[->] (Q_1) edge node [left]  {\alert{$0,1$}} (Q_2);
+\path[->] (Q_0) edge [loop right] node  {\alert{$0,1$}} ();
+%\path[->] (Q_1) edge [loop above] node  {\alert{$a$}} ();
+%\path[->] (Q_2) edge [loop below] node  {\alert{$b$}} ();
+\end{tikzpicture}
+\end{center}
+\end{textblock}
+
+\begin{textblock}{11}(6.5,4)
+\begin{tabular}{r|cl}
+nodes \textcolor{white}{*} & $0$ & $1$\\
+\hline
+$\{\}$  \textcolor{white}{*} & \onslide<2->{$\{\}$} & \onslide<2->{$\{\}$}\\
+\onslide<5->{s:} $\{0\}$ \textcolor{white}{*} & \onslide<3->{$\{0\}$} & \onslide<3->{$\{0,1\}$}\\
+$\{1\}$ \textcolor{white}{*} & \onslide<3->{$\{2\}$} & \onslide<3->{$\{2\}$}\\
+$\{2\}$ \onslide<5->{*} & \onslide<3->{$\{\}$} & \onslide<3->{$\{\}$}\\
+$\{0,1\}$ \textcolor{white}{*} &\onslide<4->{$\{0,2\}$} & \onslide<4->{$\{0,1,2\}$}\\
+$\{0,2\}$ \onslide<5->{*} &\onslide<4->{$\{0\}$} & \onslide<4->{$\{0,1\}$}\\
+$\{1,2\}$ \onslide<5->{*} & \onslide<4->{$\{2\}$} & \onslide<4->{$\{2\}$}\\
+$\{0,1,2\}$ \onslide<5->{*}& \onslide<4->{$\{0,2\}$} & \onslide<4->{$\{0,1,2\}$}\\
+\end{tabular}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
   
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{The Result}
+
+\footnotesize
+\begin{center}
+\begin{tikzpicture}[scale=0.5,>=stealth',very thick,
+                    every state/.style={minimum size=0pt,
+                    draw=blue!50,very thick,fill=blue!20},
+                    baseline=0mm]
+\node[state,initial]  (q0)  {$\{0\}$};
+\node[state] (q01) [right=of q0] {$\{0,1\}$};
+\node[state,accepting] (q12) [above=of q01] {$\{1,2\}$};
+\node[state,accepting] (q02) [below=of q01] {$\{0,2\}$};
+\node[state] (q1) [right=2cm of q12] {$\{1\}$};
+\node[state,accepting] (q2) [right=2.5cm of q01] {$\{2\}$};
+\node[state,accepting] (q012) [right=1.5cm of q02] {$\{0,1,2\}$};
+\node[state] (Qn) [right=of q2] {$\{\}$};
+
+\path[->] (q0) edge [loop above] node  {\alert{$0$}} ();
+\path[->] (q0) edge node [above]  {\alert{$1$}} (q01);
+\path[->] (q02) edge [bend left] node [left]  {\alert{$1$}} (q01);
+\path[->] (q02) edge node [below]  {\alert{$0$}} (q0);
+\path[->] (q01) edge node [above]  {\alert{$1$}} (q012);
+\path[->] (q01) edge [bend left] node [right]  {\alert{$0$}} (q02);
+\path[->] (q12) edge node [below]  {\alert{$0,1$}} (q2);
+\path[->] (q1) edge node [right]  {\alert{$0,1$}} (q2);
+\path[->] (q2) edge node [above]  {\alert{$0,1$}} (Qn);
+\path[->] (q012) edge [loop right] node  {\alert{$1$}} ();
+\path[->] (q012) edge node [below]  {\alert{$0$}} (q02);
+\path[->] (Qn) edge [loop above] node  {$\alert{0},\alert{1}$} ();
+\end{tikzpicture}
+\end{center}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Removing Dead States}
+
+\footnotesize
+\begin{center}
+\begin{tabular}{ll}
+\large DFA: & \large (original) NFA:\\
+\raisebox{0mm}{%
+\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
+                    every state/.style={minimum size=0pt,
+                    draw=blue!50,very thick,fill=blue!20}]
+\node[state,initial]  (q0)  {$\{0\}$};
+\node[state] (q01) [right=of q0] {$\{0,1\}$};
+\node[state,accepting] (q02) [below=of q01] {$\{0,2\}$};
+\node[state,accepting] (q012) [right=1.5cm of q02] {$\{0,1,2\}$};
+
+\path[->] (q0) edge [loop above] node  {\alert{$0$}} ();
+\path[->] (q0) edge node [above]  {\alert{$1$}} (q01);
+\path[->] (q02) edge [bend left] node [left]  {\alert{$1$}} (q01);
+\path[->] (q02) edge node [below]  {\alert{$0$}} (q0);
+\path[->] (q01) edge node [above]  {\alert{$1$}} (q012);
+\path[->] (q01) edge [bend left] node [right]  {\alert{$0$}} (q02);
+\path[->] (q012) edge [loop right] node  {\alert{$1$}} ();
+\path[->] (q012) edge node [below]  {\alert{$0$}} (q02);
+\end{tikzpicture}}
+&
+\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
+                    every state/.style={minimum size=0pt,
+                      draw=blue!50,very thick,fill=blue!20},]
+\node[state,initial]  (Q_0)  {$\mbox{Q}_0$};
+\node[state] (Q_1) [below=of Q_0] {$\mbox{Q}_1$};
+\node[state, accepting] (Q_2) [below=of Q_1] {$\mbox{Q}_2$};
+
+\path[->] (Q_0) edge node [left]  {\alert{$1$}} (Q_1);
+\path[->] (Q_1) edge node [left]  {\alert{$0,1$}} (Q_2);
+\path[->] (Q_0) edge [loop right] node  {\alert{$0,1$}} ();                    
+\end{tikzpicture}
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Subset Construction}
+\frametitle{Subset Construction ($\epsilon$NFA)}
 
 
 \begin{textblock}{5}(1,1.5)
@@ -1610,13 +1729,13 @@
 
 \begin{frame}[c]
 \frametitle{Housekeeping}  
-\begin{mybox3}{}
+\begin{mybox3}{CW 2}
   The deadline for CW2 is 6 November (thanks to Arshdeep Pareek
   for pointing this out).
 \end{mybox3}
 \end{frame}
 
-\begin{frame}[c]
+\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
@@ -1627,6 +1746,14 @@
 \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}
+
 \end{document}
 
 %%% Local Variables: