equal
deleted
inserted
replaced
4 import $file.nfa, nfa._ |
4 import $file.nfa, nfa._ |
5 |
5 |
6 // a fixpoint construction |
6 // a fixpoint construction |
7 import scala.annotation.tailrec |
7 import scala.annotation.tailrec |
8 @tailrec |
8 @tailrec |
9 def fixpT[A](f: A => A, x: A): A = { |
9 def fixpT[S](f: S => S, x: S): S = { |
10 val fx = f(x) |
10 val fx = f(x) |
11 if (fx == x) x else fixpT(f, fx) |
11 if (fx == x) x else fixpT(f, fx) |
12 } |
12 } |
13 |
13 |
14 // translates eNFAs directly into NFAs |
14 // translates eNFAs directly into NFAs |
47 case (Q0, None) => Set(Q1, Q2) |
47 case (Q0, None) => Set(Q1, Q2) |
48 case (Q1, Some('a')) => Set(Q1) |
48 case (Q1, Some('a')) => Set(Q1) |
49 case (Q2, Some('b')) => Set(Q2) |
49 case (Q2, Some('b')) => Set(Q2) |
50 } |
50 } |
51 |
51 |
52 val enfa1 = eNFA(Set[State](Q0), enfa_trans1, Set[State](Q2)) |
52 val nfa1 = |
|
53 eNFA(Set[State](Q0), enfa_trans1, Set[State](Q2)) |
53 |
54 |
54 |
55 |
55 // |
56 // more examples |
56 case object R1 extends State |
57 case object R1 extends State |
57 case object R2 extends State |
58 case object R2 extends State |
58 case object R3 extends State |
59 case object R3 extends State |
59 |
60 |
60 val enfa_trans2 : (State, Option[Char]) :=> Set[State] = |
61 val enfa_trans2 : (State, Option[Char]) :=> Set[State] = |
62 case (R1, None) => Set(R2) |
63 case (R1, None) => Set(R2) |
63 case (R2, Some('a')) => Set(R1, R3) |
64 case (R2, Some('a')) => Set(R1, R3) |
64 } |
65 } |
65 |
66 |
66 |
67 |
67 val enfa2 = eNFA(Set[State](R1), enfa_trans1, Set[State](R3)) |
68 val nfa2 = |
|
69 eNFA(Set[State](R1), enfa_trans1, Set[State](R3)) |