// 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