// NFAs in Scala using partial functions (returning+ −
// sets of states)+ −
//+ −
// needs :load dfa.scala for states+ −
+ −
+ −
// 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)+ −
}+ −