equal
deleted
inserted
replaced
58 enfa2.fins) |
58 enfa2.fins) |
59 } |
59 } |
60 |
60 |
61 // alternative of two NFAs |
61 // alternative of two NFAs |
62 def NFA_ALT(enfa1: NFAt, enfa2: NFAt) : NFAt = { |
62 def NFA_ALT(enfa1: NFAt, enfa2: NFAt) : NFAt = { |
63 val Q = TState() |
63 val new_delta : NFAtrans = { |
64 val new_delta : eNFAtrans = |
64 case (q, c) => applyOrElse(enfa1.delta, (q, c)) | |
65 { case (Q, None) => enfa1.starts | enfa2.starts } |
65 applyOrElse(enfa2.delta, (q, c)) } |
66 val new_fins = (q: TState) => enfa1.fins(q) || enfa2.fins(q) |
66 val new_fins = (q: TState) => enfa1.fins(q) || enfa2.fins(q) |
67 |
67 |
68 eNFA(Set(Q), new_delta +++ enfa1.delta +++ enfa2.delta, new_fins) |
68 NFA(enfa1.starts | enfa2.starts, new_delta, new_fins) |
69 } |
69 } |
70 |
70 |
71 // star of a NFA |
71 // star of a NFA |
72 def NFA_STAR(enfa: NFAt) : NFAt = { |
72 def NFA_STAR(enfa: NFAt) : NFAt = { |
73 val Q = TState() |
73 val Q = TState() |
122 |
122 |
123 // Test Cases |
123 // Test Cases |
124 |
124 |
125 |
125 |
126 // the evil regular expression a?{n} a{n} |
126 // the evil regular expression a?{n} a{n} |
127 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
127 def EVIL1(n: Int) : Rexp = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
128 |
128 |
129 // the evil regular expression (a*)*b |
129 // the evil regular expression (a*)*b |
130 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
130 val EVIL2 : Rexp = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
131 |
131 |
132 //for measuring time |
132 //for measuring time |
133 def time_needed[T](i: Int, code: => T) = { |
133 def time_needed[T](i: Int, code: => T) = { |
134 val start = System.nanoTime() |
134 val start = System.nanoTime() |
135 for (j <- 1 to i) code |
135 for (j <- 1 to i) code |
138 } |
138 } |
139 |
139 |
140 // the size of the NFA can be large, |
140 // the size of the NFA can be large, |
141 // thus slowing down the breadth-first search |
141 // thus slowing down the breadth-first search |
142 |
142 |
143 for (i <- 1 to 10) { |
143 for (i <- 1 to 13) { |
144 println(i + ": " + "%.5f".format(time_needed(2, tmatches(EVIL1(i), "a" * i)))) |
144 println(i + ": " + "%.5f".format(time_needed(2, tmatches(EVIL1(i), "a" * i)))) |
145 } |
145 } |
146 |
146 |
147 for (i <- 1 to 10) { |
147 for (i <- 1 to 100 by 5) { |
148 println(i + " " + "%.5f".format(time_needed(2, tmatches(EVIL2, "a" * i)))) |
148 println(i + " " + "%.5f".format(time_needed(2, tmatches(EVIL2, "a" * i)))) |
149 } |
149 } |
150 |
150 |
151 |
151 |
152 // the backtracking needed in depth-first search |
152 // the backtracking needed in depth-first search |