// epsilon NFAs...immediately translated into NFAs
// (needs nfa.scala)

// fixpoint construction
import scala.annotation.tailrec
@tailrec
def fixpT[A](f: A => A, x: A): A = {
  val fx = f(x)
  if (fx == x) x else fixpT(f, fx) 
}

// translates eNFAs directly into NFAs 
def eNFA[A, C](starts: Set[A],                     // starting states
               delta: (A, Option[C]) :=> Set[A],   // epsilon-transitions
               fins: A => Boolean) : NFA[A, C] = { // final states 

  // epsilon transitions
  def enext(q: A) : Set[A] = 
    applyOrElse(delta, (q, None))

  def enexts(qs: Set[A]) : Set[A] = 
    qs | qs.flatMap(enext(_))     // | is the set-union in Scala

  // epsilon closure
  def ecl(qs: Set[A]) : Set[A] = 
    fixpT(enexts, qs)

  // "normal" transitions
  def next(q: A, c: C) : Set[A] = 
    applyOrElse(delta, (q, Some(c)))

  def nexts(qs: Set[A], c: C) : Set[A] = 
    ecl(ecl(qs).flatMap(next(_, c)))

  // result NFA
  NFA(ecl(starts), 
      { case (q, c) => nexts(Set(q), c) }, 
      q => ecl(Set(q)) exists fins)
}