1 // epsilon NFAs...immediately translated into NFAs

     2 // (needs nfa.scala)

     3 

     4 // fixpoint construction

     5 import scala.annotation.tailrec

     6 @tailrec

     7 def fixpT[A](f: A => A, x: A): A = {

     8   val fx = f(x)

     9   if (fx == x) x else fixpT(f, fx) 

    10 }

    11 

    12 // translates eNFAs directly into NFAs 

    13 def eNFA[A, C](starts: Set[A],                     // starting states

    14                delta: (A, Option[C]) :=> Set[A],   // epsilon-transitions

    15                fins: A => Boolean) : NFA[A, C] = { // final states 

    16 

    17   // epsilon transitions

    18   def enext(q: A) : Set[A] = 

    19     applyOrElse(delta, (q, None))

    20 

    21   def enexts(qs: Set[A]) : Set[A] = 

    22     qs | qs.flatMap(enext(_))

    23 

    24   // epsilon closure

    25   def ecl(qs: Set[A]) : Set[A] = 

    26     fixpT(enexts, qs)

    27 

    28   // "normal" transitions

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

    30     applyOrElse(delta, (q, Some(c)))

    31 

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

    33     ecl(ecl(qs).flatMap(next(_, c)))

    34 

    35   // result NFA

    36   NFA(ecl(starts), 

    37       { case (q, c) => nexts(Set(q), c) }, 

    38       q => ecl(Set(q)) exists fins)

    39 }