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