equal
deleted
inserted
replaced
1 // epsilon NFAs...immediately translated into NFAs |
1 // epsilon NFAs...immediately translated into NFAs |
2 // (needs nfa.scala) |
2 // (needs :load nfa.scala in REPL) |
3 |
3 |
4 // fixpoint construction |
4 // fixpoint construction |
5 import scala.annotation.tailrec |
5 import scala.annotation.tailrec |
6 @tailrec |
6 @tailrec |
7 def fixpT[A](f: A => A, x: A): A = { |
7 def fixpT[A](f: A => A, x: A): A = { |
35 // result NFA |
35 // result NFA |
36 NFA(ecl(starts), |
36 NFA(ecl(starts), |
37 { case (q, c) => nexts(Set(q), c) }, |
37 { case (q, c) => nexts(Set(q), c) }, |
38 q => ecl(Set(q)) exists fins) |
38 q => ecl(Set(q)) exists fins) |
39 } |
39 } |
|
40 |
|
41 |
|
42 // eNFA examples |
|
43 val enfa_trans1 : (State, Option[Char]) :=> Set[State] = |
|
44 { case (Q0, Some('a')) => Set(Q0) |
|
45 case (Q0, None) => Set(Q1, Q2) |
|
46 case (Q1, Some('a')) => Set(Q1) |
|
47 case (Q2, Some('b')) => Set(Q2) |
|
48 } |
|
49 |
|
50 val enfa1 = eNFA(Set[State](Q0), enfa_trans1, Set[State](Q2)) |
|
51 |
|
52 |
|
53 // |
|
54 case object R1 extends State |
|
55 case object R2 extends State |
|
56 case object R3 extends State |
|
57 |
|
58 val enfa_trans2 : (State, Option[Char]) :=> Set[State] = |
|
59 { case (R1, Some('b')) => Set(R3) |
|
60 case (R1, None) => Set(R2) |
|
61 case (R2, Some('a')) => Set(R1, R3) |
|
62 } |
|
63 |
|
64 |
|
65 val enfa2 = eNFA(Set[State](R1), enfa_trans1, Set[State](R3)) |