Binary file Literature/ext-partial-ders2.pdf has changed

--- a/progs/scala/autos.scala	Tue Mar 21 11:40:22 2017 +0000
+++ b/progs/scala/autos.scala	Wed Mar 29 05:50:38 2017 +0800
@@ -253,6 +253,7 @@
 case class NTIMES(r: Rexp, n: Int) extends Rexp 
 case class UPNTIMES(r: Rexp, n: Int) extends Rexp 
 case class NOT(r: Rexp) extends Rexp
+case class AND(r1: Rexp, r2: Rexp) extends Rexp 
 
 def get_chars(r: Rexp) : Set[Char] = r match {
   case ZERO => Set()
@@ -265,6 +266,7 @@
   case UPNTIMES(r, _) => get_chars(r)
   case ALL => ('a' to 'z').toSet ++ Set('*','/','\\')
   case NOT(r) => get_chars(r)
+  case AND(r1, r2) => get_chars(r1) ++ get_chars(r2)
 }
 
 
@@ -309,6 +311,7 @@
   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 r => r
 }
 
@@ -326,6 +329,7 @@
   case NTIMES(r, i) => if (i == 0) true else nullable(r)
   case UPNTIMES(r: Rexp, n: Int) => true
   case NOT(r) => !nullable(r)
+  case AND(r1, r2) => nullable(r1) && nullable(r2)
 }
 
 // derivative of a regular expression w.r.t. a character
@@ -347,10 +351,12 @@
     if (i == 0) ZERO
     else SEQ(der(c, r1), UPNTIMES(r1, i - 1)) 
   case NOT(r) => NOT(der(c, r))
+  // AND case?
 }
 
 
 // partial derivative of a regular expression w.r.t. a character
+// does not work for NOT and AND ... see below
 def pder(c: Char, r: Rexp) : Set[Rexp] = r match {
   case ZERO => Set()
   case ONE => Set()
@@ -372,8 +378,6 @@
     if (i == 0) Set()
     else 
       for (pr1 <- pder(c, r1)) yield SEQ(pr1, UPNTIMES(r1, i - 1))
-  case NOT(r1) => 
-    for (pr1 <- pder(c, r1)) yield NOT(pr1)
 }
 
 def ppder(c: Char, rs: Set[Rexp]) : Set[Rexp] =
@@ -392,6 +396,43 @@
 } 
 
 
+
+
+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 not_add(rss: Set[Set[Rexp]]) : Set[Set[Set[Rexp]]] =
+  for (rs <- rss) yield (for (r <- rs) yield (Set(NOT(r)) : Set[Rexp]))
+
+def and_compose(rss1: Set[Set[Rexp]], rss2: Set[Set[Rexp]]) : Set[Set[Rexp]] =
+  for (rs1 <- rss1; rs2 <- rss2) yield rs1 ++ rs2
+
+def pder2(c: Char, r: Rexp) : Set[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 ALT(r1, r2) => pder2(c, r1) ++ pder2(c, r2)
+  case SEQ(r1, r2) => {
+    val prs1 = seq_add(pder2(c, r1), r2)
+    if (nullable(r1)) (prs1 ++ pder2(c, r2)) else prs1
+  }
+  case STAR(r1) => 
+    seq_add(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 }
+  }
+}
+
+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)
+} 
+
+
 // quick-and-dirty translation of a pder automaton 
 
 val r = STAR(ALL) ~ "a" ~ NTIMES(ALL, 3) ~ "bc"
@@ -553,6 +594,12 @@
 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
+
 // example from automata paper with counters and backreferences
 
 val r1 = STAR(ALL) ~ "a" ~ NTIMES(ALL, 1) ~ "bc"