// NFAs in Scala using partial functions (returning

// sets of states)

import scala.util.Try

// type abbreviation for partial functions

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

// return an empty set when not defined

def applyOrElse[A, B](f: A :=> Set[B], x: A) : Set[B] =

  Try(f(x)) getOrElse Set[B]()

// NFAs

case class NFA[A, C](starts: Set[A],           // starting states

                     delta: (A, C) :=> Set[A], // transition function

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

  // given a state and a character, what is the set of 

  // next states? if there is none => empty set

  def next(q: A, c: C) : Set[A] = 

    applyOrElse(delta, (q, c))

  def nexts(qs: Set[A], c: C) : Set[A] =

    qs.flatMap(next(_, c))

  // given some states and a string, what is the set 

  // of next states?

  def deltas(qs: Set[A], s: List[C]) : Set[A] = s match {

    case Nil => qs

    case c::cs => deltas(nexts(qs, c), cs)

  }

  // is a string accepted by an NFA?

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

    deltas(starts, s).exists(fins)

}