Binary file coursework/cw03.pdf has changed

--- a/coursework/cw03.tex	Wed Dec 06 00:06:37 2017 +0000
+++ b/coursework/cw03.tex	Thu Dec 07 12:26:41 2017 +0000
@@ -26,7 +26,7 @@
 \subsection*{Question 1}
 
 Design a grammar for the WHILE language and give the grammar
-rules. The main categories of non-terminal should be:
+rules. The main categories of non-terminals should be:
 
 \begin{itemize}
 \item arithmetic expressions (with the operations from the

--- a/progs/re3.scala	Wed Dec 06 00:06:37 2017 +0000
+++ b/progs/re3.scala	Thu Dec 07 12:26:41 2017 +0000
@@ -11,12 +11,6 @@
 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 
-case class CSET(cs: Set[Char]) extends Rexp
-case class CFUN(f: Char => Bool) extends Rexp
-
-CSET(('a' to 'z').toSet)
-
-val CSET2(cs: Set[Char]) = CFUN((c:Char) => cs.contains(c))
 
 
 // nullable function: tests whether the regular 
@@ -79,8 +73,8 @@
 
 // Test Cases
 
-//evil regular expressions
-def EVIL1(n: Int) = SEQ(NTIMEemacs re3S(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
+//evil regular expressions: (a?){n} a{n}  and (a*)* b
+def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
 
 
@@ -133,3 +127,19 @@
 size(ders("aaa".toList, EVIL2))   // 8
 size(ders("aaaa".toList, EVIL2))  // 8
 size(ders("aaaaa".toList, EVIL2)) // 8
+
+
+
+
+
+// Examples from the Sulzmann paper
+val sulzmann = STAR(ALT(ALT(CHAR('a'), CHAR('b')), SEQ(CHAR('a'), CHAR('b'))))
+
+
+for (i <- 1 to 4501 by 500) {
+  println(i + ": " + "%.5f".format(time_needed(1, matcher(sulzmann, "a" * i))))
+}
+
+for (i <- 1 to 4501 by 500) {
+  println(i + ": " + "%.5f".format(time_needed(1, matcher(sulzmann, "ab" * i))))
+}