progs/nfa.scala
changeset 485 bd6d999ab7b6
parent 483 6f508bcdaa30
child 487 a697421eaa04
equal deleted inserted replaced
484:e61ffb28994d 485:bd6d999ab7b6
     1 // NFAs in Scala based on sets of partial functions
     1 // NFAs in Scala using partial functions (returning
       
     2 // sets of states)
       
     3 import scala.util.Try
     2 
     4 
     3 // type abbreviation for partial functions
     5 // type abbreviation for partial functions
     4 type :=>[A, B] = PartialFunction[A, B]
     6 type :=>[A, B] = PartialFunction[A, B]
     5 
     7 
       
     8 // return an empty set when not defined
       
     9 def applyOrElse[A, B](f: A :=> Set[B], x: A) : Set[B] =
       
    10   Try(f(x)) getOrElse Set[B]()
       
    11 
       
    12 
       
    13 // NFAs
     6 case class NFA[A, C](starts: Set[A],            // starting states
    14 case class NFA[A, C](starts: Set[A],            // starting states
     7                      delta: Set[(A, C) :=> A],  // transitions
    15                      delta: (A, C) :=> Set[A],  // transition function
     8                      fins:  A => Boolean) {     // final states 
    16                      fins:  A => Boolean) {     // final states 
     9 
    17 
    10   // given a state and a character, what is the set of next states?
    18   // given a state and a character, what is the set of 
    11   // if there is none => empty set
    19   // next states? if there is none => empty set
    12   def next(q: A, c: C) : Set[A] = 
    20   def next(q: A, c: C) : Set[A] = 
    13     delta.flatMap(d => Try(d(q, c)).toOption)
    21     applyOrElse(delta, (q, c))
    14 
    22 
    15   def nexts(qs: Set[A], c: C) : Set[A] =
    23   def nexts(qs: Set[A], c: C) : Set[A] =
    16     qs.flatMap(next(_, c))
    24     qs.flatMap(next(_, c))
    17 
    25 
       
    26   // given some states and a string, what is the set 
       
    27   // of next states?
    18   def deltas(qs: Set[A], s: List[C]) : Set[A] = s match {
    28   def deltas(qs: Set[A], s: List[C]) : Set[A] = s match {
    19     case Nil => qs
    29     case Nil => qs
    20     case c::cs => deltas(nexts(qs, c), cs)
    30     case c::cs => deltas(nexts(qs, c), cs)
    21   }
    31   }
    22 
    32 
       
    33   // is a string accepted by an NFA?
    23   def accepts(s: List[C]) : Boolean = 
    34   def accepts(s: List[C]) : Boolean = 
    24     deltas(starts, s).exists(fins)
    35     deltas(starts, s).exists(fins)
    25 }
    36 }
    26