def simp(r: Rexp): Rexp = r match {
case ALT(r1, r2) => {
(simp(r1), simp(r2)) match {
case (NULL, r2s) => r2s
case (r1s, NULL) => r1s
case (r1s, r2s) => if (r1s == r2s) r1s else ALT(r1s, r2s)
}
}
case SEQ(r1, r2) => {
(simp(r1), simp(r2)) match {
case (NULL, _) => NULL
case (_, NULL) => NULL
case (EMPTY, r2s) => r2s
case (r1s, EMPTY) => r1s
case (r1s, r2s) => SEQ(r1s, r2s)
}
}
case NTIMES(r, n) => NTIMES(simp(r), n)
case r => r
}
def ders (s: List[Char], r: Rexp) : Rexp = s match {
case Nil => r
case c::s => ders(s, simp(der(c, r)))
}