// Another automaton construction+ −
//================================+ −
+ −
import $file.dfa, dfa._ + −
+ −
// regular expressions+ −
abstract class Rexp+ −
case object ZERO extends Rexp // matches nothing+ −
case object ONE extends Rexp // matches the empty string+ −
case class CHAR(c: Char) extends Rexp // matches a character c+ −
case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative+ −
case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence+ −
case class STAR(r: Rexp) extends Rexp // star+ −
+ −
// the nullable function: tests whether the regular + −
// expression can recognise the empty string+ −
def nullable (r: Rexp) : Boolean = r match {+ −
case ZERO => false+ −
case ONE => true+ −
case CHAR(_) => false+ −
case ALT(r1, r2) => nullable(r1) || nullable(r2)+ −
case SEQ(r1, r2) => nullable(r1) && nullable(r2)+ −
case STAR(_) => true+ −
}+ −
+ −
// the derivative of a regular expression w.r.t. a character+ −
def der (c: Char, r: Rexp) : Rexp = r match {+ −
case ZERO => ZERO+ −
case ONE => ZERO+ −
case CHAR(d) => if (c == d) ONE else ZERO+ −
case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))+ −
case SEQ(r1, r2) => + −
if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))+ −
else SEQ(der(c, r1), r2)+ −
case STAR(r1) => SEQ(der(c, r1), STAR(r1))+ −
}+ −
+ −
+ −
def flaw(r: Rexp) : DFA[Rexp, Char] = {+ −
DFA(r, + −
{ case (r, c) => der(c, r) }, + −
nullable(_))+ −
}+ −
+ −
val r = STAR(CHAR('a'))+ −
val pseudo = flaw(r)+ −
println(pseudo.accepts("".toList)) // true+ −
println(pseudo.accepts("a".toList)) // true+ −
println(pseudo.accepts("aa".toList)) // true+ −
println(pseudo.accepts("bb".toList)) // false+ −