// DFAs in Scala using partial functions

import scala.util.Try

// a type abbreviation for partial functions

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

// main DFA class

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