diff -r e61ffb28994d -r bd6d999ab7b6 progs/enfa.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/enfa.scala Tue Apr 25 12:28:07 2017 +0100 @@ -0,0 +1,39 @@ +// 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(_)) + + // 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) +}