1 def nullable (r: Rexp) : Boolean = r match {

     2   case NULL => false

     3   case EMPTY => true

     4   case CHAR(_) => false

     5   case ALT(r1, r2) => nullable(r1) || nullable(r2)

     6   case SEQ(r1, r2) => nullable(r1) && nullable(r2)

     7   case STAR(_) => true

     8 }