// a class for deterministic finite automata,// the type of states is kept polymorphiccase 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]) : Either[A, String] = if (states.contains(q)) cs match { case Nil => Left(q) case c::cs => if (delta.isDefinedAt(q, c)) deltas(delta(q, c), cs) else Right(q + " does not have a transition for " + c) } else Right(q + " is not a state of the automaton") // wether a string is accepted by the automaton def accepts(s: String) = deltas(start, s.toList) match { case Left(q) => fins.contains(q) case _ => false } }// translating a regular expression into a finite// automatonabstract class Rexpcase object NULL extends Rexpcase object EMPTY extends Rexpcase class CHAR(c: Char) extends Rexp case class ALT(r1: Rexp, r2: Rexp) extends Rexpcase class SEQ(r1: Rexp, r2: Rexp) extends Rexp case class STAR(r: Rexp) extends Rexpimplicit 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 expressionstype State = Rexptype States = Set[State]type Transition = Map[(State, Char), State]// we use as an alphabet all lowercase lettersval alphabet = "abcdefghijklmnopqrstuvwxyz".toSetdef goto(q: State, c: Char, qs: States, delta: Transition) : (States, Transition) = { val q_der : State = der(q, c) if (qs.contains(q_der)) (qs, delta + ((q, c) -> q)) else explore(qs + q_der, delta + ((q, c) -> q_der), q_der)}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"))A.startA.states.toList.lengthprintln(A.accepts("bd"))println(A.accepts("ab"))println(A.accepts("ac"))val r1 = STAR(ALT("a","b"))val r2 = SEQ("b","b")val r3 = SEQ(SEQ(SEQ(r1, r2), r1), "a")val B = mk_automaton(r3)B.startB.states.toList.length