1 // DFAs in Scala  using partial functions

     1 // DFAs in Scala  using partial functions

     2 import scala.util.Try

     2 import scala.util.Try

     3 

     3 

     4 // type abbreviation for partial functions

     4 // type abbreviation for partial functions

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

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

     6 

     7 

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

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

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

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

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

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

    10 

    11 

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

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

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

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

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

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

    39 

    40 

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

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

    41 

    43 

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

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

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

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

    45 

    47 

    46 // another DFA test with a Sink state

    48 // another DFA test with a Sink state

    47 abstract class S

    49 abstract class S

    48 case object S0 extends S

    50 case object S0 extends S

    49 case object S1 extends S

    51 case object S1 extends S