+
−
// a class for deterministic finite automata,+
−
// the type of states is kept polymorphic+
−
+
−
case class Automaton[A](start: A, states: Set[A], delta: Map[(A, Char), A], fins: Set[A]) {+
−
+
−
  // the transition function lifted to list of characters+
−
  def deltas(q: A, cs: List[Char]) : A = +
−
    if (states.contains(q)) cs match {+
−
      case Nil => q+
−
      case c::cs => +
−
        if (delta.isDefinedAt(q, c)) deltas(delta(q, c), cs)+
−
        else throw new RuntimeException(q + " does not have a transition for " + c)+
−
    }+
−
    else throw new RuntimeException(q + " is not a state of the automaton")+
−
+
−
  // wether a string is accepted by the automaton+
−
  def accepts(s: String) = +
−
    try {+
−
      fins.contains(deltas(start, s.toList))+
−
    } catch {+
−
      case e:RuntimeException => false+
−
    }+
−
}+
−
+
−
+
−
+
−
abstract class Rexp+
−
+
−
case object NULL extends Rexp+
−
case object EMPTY extends Rexp+
−
case class CHAR(c: Char) extends Rexp +
−
case class ALT(r1: Rexp, r2: Rexp) extends Rexp+
−
case class SEQ(r1: Rexp, r2: Rexp) extends Rexp +
−
case class STAR(r: Rexp) extends Rexp+
−
+
−
implicit def string2rexp(s : String) = { +
−
  def chars2rexp (cs: List[Char]) : Rexp = cs match {+
−
    case Nil => EMPTY+
−
    case c::Nil => CHAR(c)+
−
    case c::cs => SEQ(CHAR(c), chars2rexp(cs))+
−
  }+
−
  chars2rexp(s.toList)+
−
}+
−
+
−
def nullable (r: Rexp) : Boolean = r match {+
−
  case NULL => false+
−
  case EMPTY => true+
−
  case CHAR(_) => false+
−
  case ALT(r1, r2) => nullable(r1) || nullable(r2)+
−
  case SEQ(r1, r2) => nullable(r1) && nullable(r2)+
−
  case STAR(_) => true+
−
}+
−
+
−
def der (r: Rexp, c: Char) : Rexp = r match {+
−
  case NULL => NULL+
−
  case EMPTY => NULL+
−
  case CHAR(d) => if (c == d) EMPTY else NULL+
−
  case ALT(r1, r2) => ALT(der(r1, c), der(r2, c))+
−
  case SEQ(r1, r2) => if (nullable(r1)) ALT(SEQ(der(r1, c), r2), der(r2, c))+
−
                      else SEQ(der(r1, c), r2)+
−
  case STAR(r) => SEQ(der(r, c), STAR(r))+
−
}+
−
+
−
+
−
// Here we construct an automaton whose+
−
// states are regular expressions+
−
type State = Rexp+
−
type States = Set[State]+
−
type Transition =  Map[(State, Char), State]+
−
+
−
def goto(q: State, c: Char, qs: States, delta: Transition) : (States, Transition) = {+
−
  val qc : State = der(q, c)+
−
  if (qs.contains(qc)) (qs, delta + ((q, c) -> q))+
−
  else explore(qs + qc, delta + ((q, c) -> qc), qc)+
−
}+
−
+
−
// we use as alphabet all lowercase letters+
−
val alphabet = "abcdefghijklmnopqrstuvwxyz".toSet+
−
   +
−
def explore (qs: States, delta: Transition, q: State) : (States, Transition) =+
−
  alphabet.foldRight[(States, Transition)] (qs, delta) ((c, qsd) => goto(q, c, qsd._1, qsd._2)) +
−
+
−
+
−
def mk_automaton (r: Rexp) : Automaton[Rexp] = {+
−
  val (qs, delta) = explore(Set(r), Map(), r);+
−
  val fins = for (q <- qs if nullable(q)) yield q;+
−
  Automaton[Rexp](r, qs, delta, fins)+
−
}+
−
+
−
val A = mk_automaton(ALT("ab","ac"))+
−
+
−
println(A.accepts("bd"))+
−
println(A.accepts("ab"))+
−
println(A.accepts("ac"))+
−