diff -r 14a348d050b3 -r 084e2843f478 progs/display/enfa.scala --- 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) -}