--- a/progs/display/enfa.scala Tue Jul 21 00:12:34 2020 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,39 +0,0 @@
-// epsilon NFAs...immediately translated into NFAs
-// (needs dfa.scala and 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)
-}