1 // epsilon NFAs...immediately translated into NFAs |
|
2 // (needs :load dfa.scala |
|
3 // :load nfa.scala in REPL) |
|
4 |
|
5 // a fixpoint construction |
|
6 import scala.annotation.tailrec |
|
7 @tailrec |
|
8 def fixpT[A](f: A => A, x: A): A = { |
|
9 val fx = f(x) |
|
10 if (fx == x) x else fixpT(f, fx) |
|
11 } |
|
12 |
|
13 // translates eNFAs directly into NFAs |
|
14 def eNFA[A, C](starts: Set[A], // the starting states |
|
15 delta: (A, Option[C]) :=> Set[A], // the epsilon-transitions |
|
16 fins: A => Boolean) : NFA[A, C] = { // the final states |
|
17 |
|
18 // epsilon transitions |
|
19 def enext(q: A) : Set[A] = |
|
20 applyOrElse(delta, (q, None)) |
|
21 |
|
22 def enexts(qs: Set[A]) : Set[A] = |
|
23 qs | qs.flatMap(enext(_)) // | is the set-union in Scala |
|
24 |
|
25 // epsilon closure |
|
26 def ecl(qs: Set[A]) : Set[A] = |
|
27 fixpT(enexts, qs) |
|
28 |
|
29 // "normal" transitions |
|
30 def next(q: A, c: C) : Set[A] = |
|
31 applyOrElse(delta, (q, Some(c))) |
|
32 |
|
33 def nexts(qs: Set[A], c: C) : Set[A] = |
|
34 ecl(ecl(qs).flatMap(next(_, c))) |
|
35 |
|
36 // result NFA |
|
37 NFA(ecl(starts), |
|
38 { case (q, c) => nexts(Set(q), c) }, |
|
39 q => ecl(Set(q)) exists fins) |
|
40 } |
|
41 |
|
42 |
|
43 // eNFA examples |
|
44 val enfa_trans1 : (State, Option[Char]) :=> Set[State] = |
|
45 { case (Q0, Some('a')) => Set(Q0) |
|
46 case (Q0, None) => Set(Q1, Q2) |
|
47 case (Q1, Some('a')) => Set(Q1) |
|
48 case (Q2, Some('b')) => Set(Q2) |
|
49 } |
|
50 |
|
51 val enfa1 = eNFA(Set[State](Q0), enfa_trans1, Set[State](Q2)) |
|
52 |
|
53 |
|
54 // |
|
55 case object R1 extends State |
|
56 case object R2 extends State |
|
57 case object R3 extends State |
|
58 |
|
59 val enfa_trans2 : (State, Option[Char]) :=> Set[State] = |
|
60 { case (R1, Some('b')) => Set(R3) |
|
61 case (R1, None) => Set(R2) |
|
62 case (R2, Some('a')) => Set(R1, R3) |
|
63 } |
|
64 |
|
65 |
|
66 val enfa2 = eNFA(Set[State](R1), enfa_trans1, Set[State](R3)) |
|