// DFAs in Scala using partial functions+ −
import scala.util.Try+ −
+ −
// a type abbreviation for partial functions+ −
type :=>[A, B] = PartialFunction[A, B]+ −
+ −
+ −
case class DFA[A, C](start: A, // the starting state+ −
delta: (A, C) :=> A, // transitions (partial fun)+ −
fins: A => Boolean) { // the final states+ −
+ −
def deltas(q: A, s: List[C]) : A = s match {+ −
case Nil => q+ −
case c::cs => deltas(delta(q, c), cs)+ −
}+ −
+ −
def accepts(s: List[C]) : Boolean = + −
Try(fins(deltas(start, s))) getOrElse false+ −
}+ −
+ −
// the example shown in the handout + −
abstract class State+ −
case object Q0 extends State+ −
case object Q1 extends State+ −
case object Q2 extends State+ −
case object Q3 extends State+ −
case object Q4 extends State+ −
+ −
val delta : (State, Char) :=> State = + −
{ case (Q0, 'a') => Q1+ −
case (Q0, 'b') => Q2+ −
case (Q1, 'a') => Q4+ −
case (Q1, 'b') => Q2+ −
case (Q2, 'a') => Q3+ −
case (Q2, 'b') => Q2+ −
case (Q3, 'a') => Q4+ −
case (Q3, 'b') => Q0+ −
case (Q4, 'a') => Q4+ −
case (Q4, 'b') => Q4 }+ −
+ −
val dfa = DFA(Q0, delta, Set[State](Q4))+ −
dfa.accepts("aaabbb".toList) + −
+ −
dfa.accepts("bbabaab".toList) // true+ −
dfa.accepts("baba".toList) // false+ −
dfa.accepts("abc".toList) // false+ −
+ −
// another DFA test with a Sink state+ −
abstract class S+ −
case object S0 extends S+ −
case object S1 extends S+ −
case object S2 extends S+ −
case object Sink extends S+ −
+ −
// a transition function with a sink state+ −
val sigma : (S, Char) :=> S = + −
{ case (S0, 'a') => S1+ −
case (S1, 'a') => S2+ −
case _ => Sink+ −
}+ −
+ −
val dfa1a = DFA(S0, sigma, Set[S](S2))+ −
+ −
dfa1a.accepts("aa".toList) // true+ −
dfa1a.accepts("".toList) // false+ −
dfa1a.accepts("ab".toList) // false+ −
+ −