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
}