// NFAs in Scala using partial functions (returning// sets of states)//// needs :load dfa.scala for states// type abbreviation for partial functionstype :=>[A, B] = PartialFunction[A, B]// return an empty set when not defineddef applyOrElse[A, B](f: A :=> Set[B], x: A) : Set[B] = Try(f(x)) getOrElse Set[B]()// NFAscase 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)}