1 // Another automaton construction

     2 //================================

     3 

     4 import $file.dfa, dfa._ 

     5 

     6 // regular expressions

     7 abstract class Rexp

     8 case object ZERO extends Rexp                    // matches nothing

     9 case object ONE extends Rexp                     // matches the empty string

    10 case class CHAR(c: Char) extends Rexp            // matches a character c

    11 case class ALT(r1: Rexp, r2: Rexp) extends Rexp  // alternative

    12 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp  // sequence

    13 case class STAR(r: Rexp) extends Rexp            // star

    14 

    15 // the nullable function: tests whether the regular 

    16 // expression can recognise the empty string

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

    18   case ZERO => false

    19   case ONE => true

    20   case CHAR(_) => false

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

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

    23   case STAR(_) => true

    24 }

    25 

    26 // the derivative of a regular expression w.r.t. a character

    27 def der (c: Char, r: Rexp) : Rexp = r match {

    28   case ZERO => ZERO

    29   case ONE => ZERO

    30   case CHAR(d) => if (c == d) ONE else ZERO

    31   case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))

    32   case SEQ(r1, r2) => 

    33     if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))

    34     else SEQ(der(c, r1), r2)

    35   case STAR(r1) => SEQ(der(c, r1), STAR(r1))

    36 }

    37 

    38 

    39 def flaw(r: Rexp) : DFA[Rexp, Char] = {

    40   DFA(r, 

    41       { case (r, c) => der(c, r) }, 

    42       nullable(_))

    43 }

    44 

    45 val r = STAR(CHAR('a'))

    46 val pseudo = flaw(r)

    47 println(pseudo.accepts("".toList))    // true

    48 println(pseudo.accepts("a".toList))   // true

    49 println(pseudo.accepts("aa".toList))  // true

    50 println(pseudo.accepts("bb".toList))  // false