1 // DFAs in Scala using partial functions

     2 import scala.util.Try

     3 

     4 // type abbreviation for partial functions

     5 type :=>[A, B] = PartialFunction[A, B]

     6 

     7 case class DFA[A, C](start: A,              // starting state

     8                      delta: (A, C) :=> A,   // transition (partial fun)

     9                      fins:  A => Boolean) { // final states

    10 

    11   def deltas(q: A, s: List[C]) : A = s match {

    12     case Nil => q

    13     case c::cs => deltas(delta(q, c), cs)

    14   }

    15 

    16   def accepts(s: List[C]) : Boolean = 

    17     Try(fins(deltas(start, s))) getOrElse false

    18 }

    19 

    20 // the example shown earlier in the handout 

    21 abstract class State

    22 case object Q0 extends State

    23 case object Q1 extends State

    24 case object Q2 extends State

    25 case object Q3 extends State

    26 case object Q4 extends State

    27 

    28 val delta : (State, Char) :=> State = 

    29   { case (Q0, 'a') => Q1

    30     case (Q0, 'b') => Q2

    31     case (Q1, 'a') => Q4

    32     case (Q1, 'b') => Q2

    33     case (Q2, 'a') => Q3

    34     case (Q2, 'b') => Q2

    35     case (Q3, 'a') => Q4

    36     case (Q3, 'b') => Q0

    37     case (Q4, 'a') => Q4

    38     case (Q4, 'b') => Q4 }

    39 

    40 val dfa = DFA(Q0, delta, Set[State](Q4))

    41 

    42 dfa.accepts("bbabaab".toList)   // true

    43 dfa.accepts("baba".toList)      // false