import scala.concurrent._+
−
import scala.concurrent.duration._+
−
import ExecutionContext.Implicits.global+
−
import scala.language.postfixOps +
−
+
−
val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))+
−
+
−
def nullable_urban (r: Rexp) : Boolean = r match {+
−
  case ZERO => false+
−
  case ONE => true+
−
  case CHAR(_) => false+
−
  case ALT(r1, r2) => nullable_urban(r1) || nullable_urban(r2)+
−
  case SEQ(r1, r2) => nullable_urban(r1) && nullable_urban(r2)+
−
  case STAR(_) => true+
−
}+
−
+
−
def der_urban (c: Char, r: Rexp) : Rexp = r match {+
−
  case ZERO => ZERO+
−
  case ONE => ZERO+
−
  case CHAR(d) => if (c == d) ONE else ZERO+
−
  case ALT(r1, r2) => ALT(der_urban(c, r1), der_urban(c, r2))+
−
  case SEQ(r1, r2) => +
−
    if (nullable_urban(r1)) ALT(SEQ(der_urban(c, r1), r2), der_urban(c, r2))+
−
    else SEQ(der_urban(c, r1), r2)+
−
  case STAR(r1) => SEQ(der_urban(c, r1), STAR(r1))+
−
}+
−
+
−
def simp_urban(r: Rexp) : Rexp = r match {+
−
  case ALT(r1, r2) => (simp_urban(r1), simp_urban(r2)) match {+
−
    case (ZERO, r2s) => r2s+
−
    case (r1s, ZERO) => r1s+
−
    case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s)+
−
  }+
−
  case SEQ(r1, r2) =>  (simp_urban(r1), simp_urban(r2)) match {+
−
    case (ZERO, _) => ZERO+
−
    case (_, ZERO) => ZERO+
−
    case (ONE, r2s) => r2s+
−
    case (r1s, ONE) => r1s+
−
    case (r1s, r2s) => SEQ(r1s, r2s)+
−
  }+
−
  case r => r+
−
}+
−
+
−
import scala.annotation.tailrec+
−
+
−
@tailrec+
−
def iterT_urban[A](n: Int, f: A => A, x: A): A = +
−
  if (n == 0) x else iterT_urban(n - 1, f, f(x)) +
−
+
−
+
−
lazy val f = Future {+
−
  assert(size(iterT_urban(20, (r: Rexp) => der_urban('a', r), EVIL_urban)) == 7340068) +
−
  assert(size(iterT_urban(20, (r: Rexp) => simp_urban(der_urban('a', r)), EVIL_urban)) == 8) +
−
}+
−
+
−
Await.result(f, 90 second)+
−