ders2
authorChengsong
Wed, 27 Nov 2019 14:15:00 +0000
changeset 92 aaa2f2b52baf
parent 91 4fd50a6844aa
child 93 d486c12deeab
ders2
Partial.scala
Spiral.scala
lex_blex_Frankensteined.scala
--- a/Partial.scala	Mon Nov 11 17:37:24 2019 +0000
+++ b/Partial.scala	Wed Nov 27 14:15:00 2019 +0000
@@ -91,10 +91,10 @@
     }
   }
   def comp(s: List[Char], t: Rexp) = {
-    //var r = internalise(t)
-    //var setr = Set(t)
+    var r = internalise(t)
+    var setr = Set(t)
     
-    /*for(i <- 0 to s.length - 1){
+    for(i <- 0 to s.length - 1){
       val mamaipi = bsimp(bder(s(i), r))
       val mamaimapi = pdps(List(s(i)), setr)
       //compare dersimp and pder w.r.t each character in string s
@@ -105,12 +105,12 @@
       mamaimapi.foreach(m => println(regx_tree(m)))
       r = mamaipi
       setr = mamaimapi 
-    }*/
+    }
     for(i <- 1 to 10)
       println(pderas(Set(t), i).size, i)
-    //val alphabet_star_t = pderas(Set(t), 10)
-    //println("all possible elements in pder (probably...): ")
-    //alphabet_star_t.foreach(r => println(regx_tree(r)))
+    val alphabet_star_t = pderas(Set(t), 10)
+    println("all possible elements in pder (probably...): ")
+    alphabet_star_t.foreach(r => println(regx_tree(r)))
   }
 }
 /*    val delta = lfs(t).map(mon => mon._2)                
--- a/Spiral.scala	Mon Nov 11 17:37:24 2019 +0000
+++ b/Spiral.scala	Wed Nov 27 14:15:00 2019 +0000
@@ -648,6 +648,7 @@
     case c::cs => if(bnullable(c)) re_close(cs, l2.tail, AALTS(List(), List(re_init, fuse(mkepsBC(c), l2.head)) ) ) 
     else re_close(cs, l2.tail, re_init)
   }
+  //HERE
   def closed_string_der(r1: ARexp, r2: ARexp, s: String): ARexp = {
     val l1 = der_seq(r1, s.toList, Nil)
     val l2 = der_seq_rev(r2, s.toList, Nil)
@@ -670,8 +671,26 @@
     //closed_string_der(r1, r2, s2)
     closed_string_der(r1, r2, s3)
   }
+
+  def string_der_test(){
+    for(i <- 0 to 10){
+      val s = rd_string_gen(alphabet_size, i).toList
+      val r = random_struct_gen(2)
+      if(ders(s, r) != ders2(s, r)){
+        println(i)
+        println(s)
+        println(r)
+        println(ders(s, r))
+        println(ders2(s,r))
+        println("neq")
+      }
+    }
+  }
+
   def main(args: Array[String]) {
-    newxp1()
+    string_der_test()
+    //comp(rd_string_gen(3,6).toList, random_struct_gen(7))
+    //newxp1()
   //contains7()
   //retrieve_encode_STARS()
     //check_all()   
--- a/lex_blex_Frankensteined.scala	Mon Nov 11 17:37:24 2019 +0000
+++ b/lex_blex_Frankensteined.scala	Wed Nov 27 14:15:00 2019 +0000
@@ -185,6 +185,43 @@
     //case PLUS(r) => SEQ(der(c, r), STAR(r))
   }
 
+  def ders (s: List[Char], r: Rexp) : Rexp = s match {
+    case Nil => r
+    case c::s => ders(s, der(c, r))
+  }
+
+def der_seqo(r:Rexp, s: List[Char],acc: List[Rexp]) : List[Rexp] = s match{
+    case Nil => acc ::: List(r)
+    case c::cs => der_seqo(der(c, r), cs, acc ::: List(r))
+  }
+  def der_seq_revo(r:Rexp, s: List[Char], acc: List[Rexp]): List[Rexp] = s match{
+    case Nil => r::acc
+    case c::cs =>der_seq_revo(r, cs, ders(s, r) :: acc  )
+  }
+  def re_closeo(l1: List[Rexp], l2: List[Rexp], re_init: Rexp): Rexp = l1 match {
+    case Nil => re_init
+    case c::cs => if(nullable(c)) re_closeo(cs, l2.tail, ALT(re_init,  l2.head)  ) 
+    else re_closeo(cs, l2.tail, re_init)
+  }
+  //HERE
+  def closed_string_dero(r1: Rexp, r2: Rexp, s: List[Char]): Rexp = {
+    val l1 = der_seqo(r1, s, Nil)
+    val l2 = der_seq_revo(r2, s, Nil)
+    val Re = re_closeo((l1.reverse).tail, l2.tail, SEQ(l1.last, l2.head))
+    Re
+  }
+  //derivative w.r.t string
+def ders2(s: List[Char], r: Rexp) : Rexp = (s, r) match {
+  case (Nil, r) => r
+  case (s, ZERO) => ZERO
+  case (s, ONE) => if (s == Nil) ONE else ZERO
+  case (s, CHAR(c)) => if (s == List(c)) ONE else 
+                       if (s == Nil) CHAR(c) else ZERO
+  case (s, ALTS(List(r1, r2))) => ALT(ders2(s, r1), ders2(s, r2))
+  case (s, SEQ(r1, r2)) => closed_string_dero(r1, r2, s)
+  case (c::cs, STAR(r)) => closed_string_dero(der(c, r), STAR(r), cs)
+}
+
   def flatten(v: Val) : String = v match {
     case Empty => ""
     case Chr(c) => c.toString
@@ -365,12 +402,6 @@
     case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r))
   }
 
-
-  def ders (s: List[Char], r: Rexp) : Rexp = s match {
-    case Nil => r
-    case c::s => ders(s, der(c, r))
-  }
-
   // derivative w.r.t. a string (iterates bder)
   @tailrec
   def bders (s: List[Char], r: ARexp) : ARexp = s match {