1 import scala.annotation.tailrec

     1 import scala.annotation.tailrec

     2 

     3 

     3 abstract class Rexp

     4 abstract class Rexp

     4 

     5 

     5 case object NULL extends Rexp

     6 case object NULL extends Rexp

     6 case object EMPTY extends Rexp

     7 case object EMPTY extends Rexp

    70   case NOT(r) => NOT(der (c, r))

    71   case NOT(r) => NOT(der (c, r))

    71   case REP(r, i) => 

    72   case REP(r, i) => 

    72     if (i == 0) NULL else SEQ(der(c, r), REP(r, i - 1))

    73     if (i == 0) NULL else SEQ(der(c, r), REP(r, i - 1))

    73 }

    74 }

    74 

    75 

    75 // derivative w.r.t. a string (iterates der)

    77 // derivative w.r.t. a string (iterates der)

    76 @tailrec

    78 @tailrec

    77 def ders (s: List[Char], r: Rexp) : Rexp = s match {

    79 def ders (s: List[Char], r: Rexp) : Rexp = s match {

    78   case Nil => r

    80   case Nil => r

    79   case c::s => ders(s, der(c, r))

    81   case c::s => ders(s, der(c, r))