# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1491070441 -28800
# Node ID dcfc9b23b263d2e2f4996a84c4020e23fcc5763e
# Parent  1075bba7b8b1ce3a698badff6710885fa227760b
added more literature about extended partial derivative automata

diff -r 1075bba7b8b1 -r dcfc9b23b263 Literature/ext-partial-ders3-phd.pdf
Binary file Literature/ext-partial-ders3-phd.pdf has changed
diff -r 1075bba7b8b1 -r dcfc9b23b263 progs/scala/autos.scala
--- a/progs/scala/autos.scala	Wed Mar 29 05:50:38 2017 +0800
+++ b/progs/scala/autos.scala	Sun Apr 02 02:14:01 2017 +0800
@@ -247,6 +247,7 @@
 case object ONE extends Rexp
 case class CHAR(c: Char) extends Rexp 
 case object ALL extends Rexp 
+case object ALLPlus 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 
@@ -299,7 +300,7 @@
   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 (r1s, r2s) => if (r1s == r2s) r1s else ALT(r1s, r2s)
   }
   case SEQ(r1, r2) =>  (simp(r1), simp(r2)) match {
     case (ZERO, _) => ZERO
@@ -310,8 +311,14 @@
   }
   case NTIMES(r, n) => if (n == 0) ONE else NTIMES(simp(r), n)
   case UPNTIMES(r, n) => if (n == 0) ONE else UPNTIMES(simp(r), n)
+  /*
   case NOT(r) => NOT(simp(r))
-  case AND(r1, r2) => AND(simp(r1), simp(r2))  
+  case AND(r1, r2) => (simp(r1), simp(r2)) match {
+    case (ALL, r2s) => r2s
+    case (r1s, ALL) => r1s
+    case (r1s, r2s) => if (r1s == r2s) r1s else AND(r1s, r2s)  
+  }
+  */
   case r => r
 }
 
@@ -322,7 +329,8 @@
   case ZERO => false
   case ONE => true
   case CHAR(_) => false
-  case ALL => false
+  case ALL => true
+  case ALLPlus => false
   case ALT(r1, r2) => nullable(r1) || nullable(r2)
   case SEQ(r1, r2) => nullable(r1) && nullable(r2)
   case STAR(_) => true
@@ -337,7 +345,8 @@
   case ZERO => ZERO
   case ONE => ZERO
   case CHAR(d) => if (c == d) ONE else ZERO
-  case ALL => ONE
+  case ALL => ALL
+  case ALLPlus => ALL 
   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))
@@ -351,7 +360,7 @@
     if (i == 0) ZERO
     else SEQ(der(c, r1), UPNTIMES(r1, i - 1)) 
   case NOT(r) => NOT(der(c, r))
-  // AND case?
+  case AND(r1, r2) => AND(der(c, r1), der(c, r2))
 }
 
 
@@ -361,7 +370,8 @@
   case ZERO => Set()
   case ONE => Set()
   case CHAR(d) => if (c == d) Set(ONE) else Set()
-  case ALL => Set(ONE)
+  case ALL => Set(ALL)
+  case ALLPlus => Set(ALL)
   case ALT(r1, r2) => pder(c, r1) ++ pder(c, r2)
   case SEQ(r1, r2) => 
     (for (pr1 <- pder(c, r1)) yield SEQ(pr1, r2)) ++ 
@@ -396,44 +406,67 @@
 } 
 
 
-
+// partial derivatives including NOT and AND according to
+// PhD-thesis: Manipulation of Extended Regular Expressions 
+// with Derivatives; these partial derivatives are also not
+// finite...for example NOT((a*)a)
 
-def seq_add(rss: Set[Set[Rexp]], r2: Rexp) : Set[Set[Rexp]] =
-  for (rs <- rss) yield (for (r <- rs) yield (SEQ(r, r2) : Rexp))
+def seq_compose(rs: Set[Rexp], r2: Rexp) : Set[Rexp] =
+  for (r <- rs) yield (SEQ(r, r2) : Rexp)
 
-def not_add(rss: Set[Set[Rexp]]) : Set[Set[Set[Rexp]]] =
-  for (rs <- rss) yield (for (r <- rs) yield (Set(NOT(r)) : Set[Rexp]))
+def not_compose(rs: Set[Rexp]) : Set[Rexp] =
+  Set(rs.fold(ALL)((r1, r2) => AND(r1, NOT(r2))))
 
-def and_compose(rss1: Set[Set[Rexp]], rss2: Set[Set[Rexp]]) : Set[Set[Rexp]] =
-  for (rs1 <- rss1; rs2 <- rss2) yield rs1 ++ rs2
+def and_compose(rs1: Set[Rexp], rs2: Set[Rexp]) : Set[Rexp] =
+  for (r1 <- rs1; r2 <- rs2) yield AND(r1, r2)
 
-def pder2(c: Char, r: Rexp) : Set[Set[Rexp]] = r match {
+def pder2(c: Char, r: Rexp) : Set[Rexp] = r match {
   case ZERO => Set()
   case ONE => Set()
-  case CHAR(d) => if (c == d) Set(Set(ONE)) else Set()
-  case ALL => Set(Set(ONE))
+  case ALL => Set(ALL)
+  case ALLPlus => Set(ALL)
+  case CHAR(d) => if (c == d) Set(ONE) else Set()
   case ALT(r1, r2) => pder2(c, r1) ++ pder2(c, r2)
   case SEQ(r1, r2) => {
-    val prs1 = seq_add(pder2(c, r1), r2)
+    val prs1 = seq_compose(pder2(c, r1), r2)
     if (nullable(r1)) (prs1 ++ pder2(c, r2)) else prs1
   }
-  case STAR(r1) => 
-    seq_add(pder2(c, r1), STAR(r1))
+  case STAR(r1) => seq_compose(pder2(c, r1), STAR(r1))
   case AND(r1, r2) => and_compose(pder2(c, r1), pder2(c, r2))
-  case NOT(r1) => {
-    val prs1 = not_add(pder2(c, r1))
-    if (prs1.isEmpty) Set() else 
-      prs1.tail.foldRight(prs1.head) { (rs1, rs2) => rs1 ++ rs2 }
-  }
+  case NOT(r1) => nder2(c, r1)
 }
 
-def pmatcher2(rss: Set[Set[Rexp]], s: List[Char]): Boolean = s match {
-  case Nil => rss.exists((rs) => rs.exists((r) => nullable(r)))
-  case c::cs => pmatcher2(rss.flatMap(_.flatMap(pder2(c, _))), cs)
+def nder2(c: Char, r: Rexp) : Set[Rexp] = r match {
+  case ZERO => Set(ALL)
+  case ONE => Set(ALL)
+  case ALL => Set()
+  case ALLPlus => Set()
+  case CHAR(d) => if (c == d) Set(ALLPlus) else Set(ALL)
+  case ALT(r1, r2) => and_compose(nder2(c, r1), nder2(c, r2))
+  case SEQ(r1, r2) => if (nullable(r1))
+                      and_compose(not_compose(seq_compose(pder2(c, r1), r2)), nder2(c, r2))
+                      else not_compose(seq_compose(pder2(c, r1), r2))
+  case STAR(r1) => not_compose(pder2(c, STAR(r1)))
+  case AND(r1, r2) => nder2(c, r1) ++ nder2(c, r2)
+  case NOT(r1) => pder2(c, r1)
+}
+
+
+def pmatcher2(rs: Set[Rexp], s: List[Char]): Boolean = s match {
+  case Nil => rs.exists(nullable(_))
+  case c::cs => pmatcher2(rs.flatMap(pder2(c, _)), cs)
 } 
 
+// pder2/nder2 example
 
-// quick-and-dirty translation of a pder automaton 
+val r_ex = AND("aa" | "a", AND(STAR("a"), NOT(STAR("a") ~ "a"))) 
+nder2('a', r_ex).map(simp(_)).mkString("\n")
+
+
+
+
+
+// quick-and-dirty translation of a pder-automaton 
 
 val r = STAR(ALL) ~ "a" ~ NTIMES(ALL, 3) ~ "bc"
 val pder_nfa = NFA[Set[Rexp], Char](Set(Set(r)), 
@@ -509,7 +542,11 @@
 
 
 
-// Antimirov Partial derivative automata construction ... definitely terminates
+// Antimirov Partial derivative automata construction ... definitely 
+// terminates but does not work for extensions of NOT and AND
+//
+// for this we have to use the extended partial derivatives
+// pder2/nder2
 
 
 // to transform (concrete) Maps into functions
@@ -517,7 +554,7 @@
   { case (q, c) => m(q, c) }
 
 def pgoto(sigma: Set[Char], delta: STrans, qs: DStates, q: DState, c: Char) : (DStates, STrans) = {
-  val qders = pder(c, q).map(simp(_))  // set of simplified partial derivatives
+  val qders = pder2(c, q).map(simp(_))  // set of simplified partial derivatives
   qders.foldLeft((qs, delta)) { case ((qs, delta), qnew) => padd(sigma, delta, qs, q, qnew, c) }
 }
 
@@ -586,19 +623,13 @@
 matcher(rnot, "/*aaabaa*/".toList)  // true
 matcher(rnot, "/*/**/".toList)      // true
 matcher(rnot, "/*aaa*/aa*/".toList) // false
-matcher(rnot, "/aaa*/aa*/".toList) // false
+matcher(rnot, "/aaa*/aa*/".toList)  // false
 
-pmatcher(Set(rnot), "/**/".toList)        // true
-pmatcher(Set(rnot), "/*aaabaa*/".toList)  // true
-pmatcher(Set(rnot), "/*/**/".toList)      // true
-pmatcher(Set(rnot), "/*aaa*/aa*/".toList) // false  ?????
-pmatcher(Set(rnot), "/aaa*/aa*/".toList) // false
-
-pmatcher2(Set(Set(rnot)), "/**/".toList)        // true
-pmatcher2(Set(Set(rnot)), "/*aaabaa*/".toList)  // true
-pmatcher2(Set(Set(rnot)), "/*/**/".toList)      // true
-pmatcher2(Set(Set(rnot)), "/*aaa*/aa*/".toList) // false  ?????
-pmatcher2(Set(Set(rnot)), "/aaa*/aa*/".toList) // false
+pmatcher2(Set(rnot), "/**/".toList)        // true
+pmatcher2(Set(rnot), "/*aaabaa*/".toList)  // true
+pmatcher2(Set(rnot), "/*/**/".toList)      // true
+pmatcher2(Set(rnot), "/*aaa*/aa*/".toList) // false
+pmatcher2(Set(rnot), "/aaa*/aa*/".toList)  // false
 
 // example from automata paper with counters and backreferences