--- a/marking4/re.scala	Mon Dec 10 02:23:30 2018 +0000
+++ b/marking4/re.scala	Fri Dec 14 14:41:54 2018 +0000
@@ -1,8 +1,9 @@
 // Part 1 about Regular Expression Matching
 //==========================================
 
-object CW8a {
+//object CW9a {
 
+// Regular Expressions
 abstract class Rexp
 case object ZERO extends Rexp
 case object ONE extends Rexp
@@ -38,10 +39,11 @@
   def ~ (r: String) = SEQ(s, r)
 }
 
-// (1a) Complete the function nullable according to
+// (1) Complete the function nullable according to
 // the definition given in the coursework; this 
 // function checks whether a regular expression
-// can match the empty string
+// can match the empty string and Returns a boolean
+// accordingly.
 
 def nullable (r: Rexp) : Boolean = r match {
   case ZERO => false
@@ -52,10 +54,10 @@
   case STAR(_) => true
 }
 
-// (1b) Complete the function der according to
+// (2) Complete the function der according to
 // the definition given in the coursework; this
 // function calculates the derivative of a 
-// regular expression w.r.t. a character
+// regular expression w.r.t. a character.
 
 def der (c: Char, r: Rexp) : Rexp = r match {
   case ZERO => ZERO
@@ -68,11 +70,12 @@
   case STAR(r1) => SEQ(der(c, r1), STAR(r1))
 }
 
-// (1c) Complete the function der according to
+// (3) Complete the simp function according to
 // the specification given in the coursework; this
-// function simplifies a regular expression;
-// however it does not simplify inside STAR-regular
-// expressions
+// function simplifies a regular expression from
+// the inside out, like you would simplify arithmetic 
+// expressions; however it does not simplify inside 
+// STAR-regular expressions.
 
 def simp(r: Rexp) : Rexp = r match {
   case ALT(r1, r2) => (simp(r1), simp(r2)) match {
@@ -90,11 +93,12 @@
   case r => r
 }
 
-// (1d) Complete the two functions below; the first 
+
+// (4) Complete the two functions below; the first 
 // calculates the derivative w.r.t. a string; the second
 // is the regular expression matcher taking a regular
 // expression and a string and checks whether the
-// string matches the regular expression
+// string matches the regular expression.
 
 def ders (s: List[Char], r: Rexp) : Rexp = s match {
   case Nil => r
@@ -102,12 +106,13 @@
 }
 
 // main matcher function
-def matcher(r: Rexp, s: String): Boolean = nullable(ders(s.toList, r))
+def matcher(r: Rexp, s: String) = nullable(ders(s.toList, r))
 
-// (1e) Complete the size function for regular
-// expressions  according to the specification 
+// (5) Complete the size function for regular
+// expressions according to the specification 
 // given in the coursework.
 
+
 def size(r: Rexp): Int = r match {
   case ZERO => 1
   case ONE => 1
@@ -120,29 +125,31 @@
 
 
 // some testing data
-/*
-matcher(("a" ~ "b") ~ "c", "abc")  // => true
-matcher(("a" ~ "b") ~ "c", "ab")   // => false
+
+//matcher(("a" ~ "b") ~ "c", "abc")  // => true
+//matcher(("a" ~ "b") ~ "c", "ab")   // => false
 
 // the supposedly 'evil' regular expression (a*)* b
 val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
 
-matcher(EVIL, "a" * 1000 ++ "b")   // => true
-matcher(EVIL, "a" * 1000)          // => false
+//matcher(EVIL, "a" * 1000 ++ "b")   // => true
+//matcher(EVIL, "a" * 1000)          // => false
 
 // size without simplifications
-size(der('a', der('a', EVIL)))             // => 28
-size(der('a', der('a', der('a', EVIL))))   // => 58
+//size(der('a', der('a', EVIL)))             // => 28
+//size(der('a', der('a', der('a', EVIL))))   // => 58
 
 // size with simplification
-size(simp(der('a', der('a', EVIL))))           // => 8
-size(simp(der('a', der('a', der('a', EVIL))))) // => 8
+//size(simp(der('a', der('a', EVIL))))           // => 8
+//size(simp(der('a', der('a', der('a', EVIL))))) // => 8
 
-// Java needs around 30 seconds for matching 28 a's with EVIL. 
+// Python needs around 30 seconds for matching 28 a's with EVIL. 
+// Java 9 and later increase this to an "astonishing" 40000 a's in
+// around 30 seconds.
 //
 // Lets see how long it takes to match strings with 
-// 0.5 Million a's...it should be in the range of some
-// seconds.
+// 5 Million a's...it should be in the range of a 
+// couple of seconds.
 
 def time_needed[T](i: Int, code: => T) = {
   val start = System.nanoTime()
@@ -151,9 +158,19 @@
   (end - start)/(i * 1.0e9)
 }
 
-for (i <- 0 to 5000000 by 500000) {
-  println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))))
-}
-*/
+//for (i <- 0 to 5000000 by 500000) {
+//  println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))) + " secs.") 
+//}
+
+// another "power" test case 
+//simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(100).next) == ONE
 
-}
+// the Iterator produces the rexp
+//
+//      SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE)
+//
+//    where SEQ is nested 100 times.
+ 
+
+
+//}