// DFAs in Scala using partial functionsimport scala.util.Try// a type abbreviation for partial functionstype :=>[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 Statecase object Q0 extends Statecase object Q1 extends Statecase object Q2 extends Statecase object Q3 extends Statecase object Q4 extends Stateval 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) // truedfa.accepts("baba".toList) // falsedfa.accepts("abc".toList) // false// another DFA test with a Sink stateabstract class Scase object S0 extends Scase object S1 extends Scase object S2 extends Scase object Sink extends S// a transition function with a sink stateval 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) // truedfa1a.accepts("".toList) // falsedfa1a.accepts("ab".toList) // false