--- a/progs/scala/re.scala	Fri Mar 13 21:27:03 2015 +0000
+++ b/progs/scala/re.scala	Fri Apr 10 22:38:36 2015 +0100
@@ -233,6 +233,51 @@
 def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList)
 
 
+// brute force infrastructure
+
+def enum(n: Int, s: String) : Set[Rexp] = n match {
+  case 0 => Set(NULL, EMPTY) ++ s.toSet.map(CHAR)
+  case n => {
+    val rs = enum(n - 1, s)
+    rs ++
+    (for (r1 <- rs; r2 <- rs) yield ALT(r1, r2)) ++
+    (for (r1 <- rs; r2 <- rs) yield SEQ(r1, r2))
+  }
+}
+
+def ord(v1: Val, r: Rexp, v2: Val) : Boolean = (v1, r, v2) match {
+  case (Void, EMPTY, Void) => true
+  case (Chr(c1), CHAR(c2), Chr(c3)) if (c1==c2 && c1==c3) => true
+  case (Left(v1), ALT(r1,r2), Left(v2)) => ord(v1,r1,v2)
+  case (Right(v1), ALT(r1,r2), Right(v2)) => ord(v1,r2,v2)
+  case (Left(v1), ALT(r1,r2), Right(v2)) => flatten(v2).length <= flatten(v1).length
+  case (Right(v1), ALT(r1,r2), Left(v2)) => flatten(v2).length < flatten(v1).length
+  case (Sequ(v1,v2), SEQ(r1,r2), Sequ(v3,v4)) if(v1==v3) => ord(v2, r2, v4)
+  case (Sequ(v1,v2), SEQ(r1,r2), Sequ(v3,v4)) if(v1!=v3) => ord(v1, r1, v3)
+  case _ => false
+}     
+
+def tst(r: Rexp, c: Char) : Set[(Rexp, Val, Val, Val, Val)] = {
+  val r_der = der(c, r)
+  val vs = values(r_der)
+  for (v1 <- vs; v2 <- vs; 
+       if (v1 != v2 && ord(v1, r_der, v2) && ord(inj(r, c, v2), r, inj(r, c, v1)))) 
+  yield (r, v1, v2, inj(r, c, v1), inj(r, c, v2))  
+}
+
+def comp(r1: (Rexp, Val, Val, Val, Val), r2: (Rexp, Val, Val, Val, Val)) = size(r1._1) < size(r2._1)
+
+
+val smallest = enum(3, "a").flatMap(tst(_, 'a')).toList.sortWith { comp }.head
+
+smallest match {
+  case (r, v1, v2, v3, v4) => List(pretty(r),
+                                   pretty(der('a', r)),
+                                   vpretty(v1),
+                                   vpretty(v2),
+                                   vpretty(v3),
+                                   vpretty(v4)).mkString("\n") }
+
 // Lexing Rules for a Small While Language
 
 def PLUS(r: Rexp) = r ~ r.%
@@ -371,7 +416,16 @@
   time(lexing_simp(WHILE_REGS, prog2 * i))
 }
 
-val a0 = (EMPTY | "a") ~ ("b" | "abc")
+
+val a0 = (EMPTY | "a") ~ (EMPTY | "ab")
+val a1 = der('a', a0)
+pretty(a1)
+val m = mkeps(a1)
+vpretty(m)
+val v = inj(a0, 'a', m)
+vpretty(v)
+
+val a0 = (EMPTY | "a") ~ (EMPTY | "ab")
 val a1 = der('a', a0)
 pretty(a1)
 values(a1).toList
@@ -381,3 +435,15 @@
 vpretty(inj(a0,'a',u1))
 vpretty(inj(a0,'a',u2))
 
+lexing(a0, "ab")
+val aa = der('a', a0)
+pretty(aa)
+val ab = der('b', aa)
+pretty(ab)
+nullable(ab)
+val m = mkeps(ab)
+vpretty(m)
+val vb = inj(aa, 'b', m)
+vpretty(vb)
+val va = inj(a0, 'a', vb)
+vpretty(va)