990 val STARREG = //((( (STAR("aa")) | STAR("aaa") ).%).%)

   989 def n_astar_list(d: Int) : Rexp = {

   990   if(d == 0) STAR("a") 

   991   else ALTS(STAR("a" * d), n_astar_list(d - 1))

   992 }

   993 def n_astar_alts(d: Int) : Rexp = d match {

   994   case 0 => n_astar_list(0)

   995   case d => STAR(n_astar_list(d))

   996   // case r1 :: r2 :: Nil => ALTS(r1, r2)

   997   // case r1 :: Nil => r1

   998   // case r :: rs => ALTS(r, n_astar_alts(rs))

   999   // case Nil => throw new Error("should give at least 1 elem")

  1000 }

  1001 def n_astar_aux(d: Int) = {

  1002   if(d == 0) n_astar_alts(0)

  1003   else ALTS(n_astar_alts(d), n_astar_alts(d - 1))

  1004 }

  1005 

  1006 def n_astar(d: Int) : Rexp = STAR(n_astar_aux(d))

  1007 //val STARREG = n_astar(3)

  1008 // ( STAR("a") | 

  1009 //                  ("a" | "aa").% | 

  1010 //                 ( "a" | "aa" | "aaa").% 

  1011 //                 ).%

  1012                 //( "a" | "aa" | "aaa" | "aaaa").% |

  1013                 //( "a" | "aa" | "aaa" | "aaaa" | "aaaaa").% 

   995 

  1018 def lcm(list: Seq[Int]):Int=list.foldLeft(1:Int){

  1019   (a, b) => b * a /

  1020   Stream.iterate((a,b)){case (x,y) => (y, x%y)}.dropWhile(_._2 != 0).head._1.abs

  1021 }

   998 

  1024   //val pderSTAR = pderUNIV(STARREG)

   999 

  1025 

  1000 //   println(lexing_simp(NOTREG, prog0))

  1026   //val refSize = pderSTAR.map(size(_)).sum

  1001 //   val v = lex_simp(NOTREG, prog0.toList)

  1027   for(n <- 6 to 6){

  1002 //   println(v)

  1028     val STARREG = n_astar(n)

  1003 

  1029     val iMax = (lcm((1 to n).toList))

  1004 //   val d =  (lex_simp(NOTREG, prog0.toList))

  1030     for(i <- 1 to iMax + 50){// 100, 400, 800, 840, 841, 900 

  1005 //   println(d)

  1031       val prog0 = "a" * i

  1006   val pderSTAR = pderUNIV(STARREG)

  1032       //println(s"test: $prog0")

  1007 

  1033       print(n)

  1008   val refSize = pderSTAR.map(size(_)).sum

  1034       print(" ")

  1009   // println("different partial derivative terms:")

  1035       // print(i)

  1010   // pderSTAR.foreach(r => r match {

  1036       // print(" ")

  1011       

  1037       println(asize(bders_simp(prog0.toList, internalise(STARREG))))

  1012   //       case SEQ(head, rstar) =>

  1038     }

  1013   //         println(shortRexpOutput(head) ++ "~STARREG")

  1039   }

  1014   //       case STAR(rstar) =>

  1015   //         println("STARREG")

  1016       

  1017   //   }

  1018   //   )

  1019   // println("the total number of terms is")

  1020   // //println(refSize)

  1021   // println(pderSTAR.size)

  1022 

  1023   // val A : Rexp= ("c" | (ONE | "b") ~ "d") ~((ONE).%)

  1024   // val B : Rexp = ((ONE).%)

  1025   // val C : Rexp = ("d") ~ ((ONE).%)

  1026   // val PRUNE_REG : Rexp = (C | B | A)

  1027   // val APRUNE_REG = internalise(PRUNE_REG)

  1028   // val program_solution = pruneRexp(APRUNE_REG, breakIntoTerms(PRUNE_REG))

  1029   // println("program executes and gives: as disired!")

  1030   // println(shortRexpOutput(erase(program_solution)))

  1031   // val simpedPruneReg = strongBsimp(APRUNE_REG)

  1032 

  1033   // println(shortRexpOutput(erase(simpedPruneReg)))

  1034 

  1035 

  1036   for(i <- List(1,2,3,4,10, 100, 400, 841, 900 ) ){// 100, 400, 800, 840, 841, 900

  1037     val prog0 = "a" * i

  1038     //println(s"test: $prog0")

  1039     println(s"testing with $i a's" )

  1040     //val bd = bdersSimp(prog0, STARREG)//DB

  1041     val sbd = bdersStrongRexp(prog0, STARREG)//strongDB

  1042     starPrint(erase(sbd))

  1043     val subTerms = breakIntoTerms(erase(sbd))

  1044     //val subTermsLarge = breakIntoTerms(erase(bd))

  1045     

  1046     println(s"subterms of regex with strongDB: ${subTerms.length}")//, standard DB: ${subTermsLarge.length}")

  1047 

  1048 

  1049 

  1050     println("the number of distinct subterms for bsimp with strongDB")

  1051     println(subTerms.distinct.size)

  1052     //println(subTermsLarge.distinct.size)

  1053     if(pderSTAR.size > subTerms.length)

  1054       println(s"which is less than or equal to the number of PDER terms: ${pderSTAR.size}")

  1055 

  1056 

  1057     // println(shortRexpOutput(erase(sbd)))

  1058     // println(shortRexpOutput(erase(bd)))

  1059     

  1060     println("pdersize, original, strongSimp")

  1061     println(refSize, size(STARREG),  asize(sbd))

  1062 

  1063     //val vres = strong_blexing_simp( STARREG, prog0)

  1064     //println(vres)

  1065   }

  1066   // println(vs.length)

  1067   // println(vs)

  1068    

  1069 

  1070   // val prog1 = """read  n; write n"""  

  1071   // println(s"test: $prog1")

  1072   // println(lexing_simp(WHILE_REGS, prog1))

  1073   // val display = ("a"| "ab").%

  1074   // val adisplay = internalise(display)

  1075   // bders_simp( "aaaaa".toList, adisplay)

  1164 // small()

  1128 small()

  1165 generator_test()

  1129 // generator_test()

  1166 

  1130 

  1167 1

  1131 // 1

  1168 

  1132 

  1169 SEQ(SEQ(SEQ(ONE,CHAR('b')),STAR(CHAR('b'))),

  1133 // SEQ(SEQ(SEQ(ONE,CHAR('b')),STAR(CHAR('b'))),

  1170 SEQ(ALTS(ALTS(ZERO,STAR(CHAR('b'))),

  1134 // SEQ(ALTS(ALTS(ZERO,STAR(CHAR('b'))),

  1171 STAR(ALTS(CHAR('a'),SEQ(SEQ(STAR(ALTS(STAR(CHAR('c')),CHAR('a'))),

  1135 // STAR(ALTS(CHAR('a'),SEQ(SEQ(STAR(ALTS(STAR(CHAR('c')),CHAR('a'))),

  1172 SEQ(CHAR('a'),SEQ(ALTS(CHAR('b'),ZERO),SEQ(ONE,CHAR('b'))))),ONE)))),ONE))

  1136 // SEQ(CHAR('a'),SEQ(ALTS(CHAR('b'),ZERO),SEQ(ONE,CHAR('b'))))),ONE)))),ONE))