1 // NFAs in Scala using partial functions (returning

     2 // sets of states)

     3 //

     4 // needs :load dfa.scala   for states

     5 

     6 

     7 // type abbreviation for partial functions

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

     9 

    10 // return an empty set when not defined

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

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

    13 

    14 

    15 // NFAs

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

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

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

    19 

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

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

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

    23     applyOrElse(delta, (q, c))

    24 

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

    26     qs.flatMap(next(_, c))

    27 

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

    29   // of next states?

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

    31     case Nil => qs

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

    33   }

    34 

    35   // is a string accepted by an NFA?

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

    37     deltas(starts, s).exists(fins)

    38 }