1 // epsilon NFAs...immediately translated into NFAs |
1 // epsilon NFAs...immediately translated into NFAs |
2 // (needs :load dfa.scala |
2 // (needs :load dfa.scala |
3 // :load nfa.scala in REPL) |
3 // :load nfa.scala in REPL) |
4 |
4 |
5 // fixpoint construction |
5 // a fixpoint construction |
6 import scala.annotation.tailrec |
6 import scala.annotation.tailrec |
7 @tailrec |
7 @tailrec |
8 def fixpT[A](f: A => A, x: A): A = { |
8 def fixpT[A](f: A => A, x: A): A = { |
9 val fx = f(x) |
9 val fx = f(x) |
10 if (fx == x) x else fixpT(f, fx) |
10 if (fx == x) x else fixpT(f, fx) |
11 } |
11 } |
12 |
12 |
13 // translates eNFAs directly into NFAs |
13 // translates eNFAs directly into NFAs |
14 def eNFA[A, C](starts: Set[A], // starting states |
14 def eNFA[A, C](starts: Set[A], // the starting states |
15 delta: (A, Option[C]) :=> Set[A], // epsilon-transitions |
15 delta: (A, Option[C]) :=> Set[A], // the epsilon-transitions |
16 fins: A => Boolean) : NFA[A, C] = { // final states |
16 fins: A => Boolean) : NFA[A, C] = { // the final states |
17 |
17 |
18 // epsilon transitions |
18 // epsilon transitions |
19 def enext(q: A) : Set[A] = |
19 def enext(q: A) : Set[A] = |
20 applyOrElse(delta, (q, None)) |
20 applyOrElse(delta, (q, None)) |
21 |
21 |