def F_ID(v: Val): Val = vdef F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v))def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v))def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { case Right(v) => Right(f2(v)) case Left(v) => Left(f1(v))}def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))}def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(Empty), f2(v))def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(v), f2(Empty))def F_ERROR(v: Val): Val = throw new Exception("error")// simplification of regular expressions returning also a// rectification function; no simplification under STAR def simp(r: Rexp): (Rexp, Val => Val) = r match { case ALT(r1, r2) => { val (r1s, f1s) = simp(r1) val (r2s, f2s) = simp(r2) (r1s, r2s) match { case (ZERO, _) => (r2s, F_RIGHT(f2s)) case (_, ZERO) => (r1s, F_LEFT(f1s)) case _ => if (r1s == r2s) (r1s, F_LEFT(f1s)) else (ALT (r1s, r2s), F_ALT(f1s, f2s)) } } case SEQ(r1, r2) => { val (r1s, f1s) = simp(r1) val (r2s, f2s) = simp(r2) (r1s, r2s) match { case (ZERO, _) => (ZERO, F_ERROR) case (_, ZERO) => (ZERO, F_ERROR) case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s)) case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s)) case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s)) } } case r => (r, F_ID)}