43 |
43 |
44 def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
44 def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
45 |
45 |
46 |
46 |
47 //optional regular expression: one or zero times |
47 //optional regular expression: one or zero times |
|
48 //this regular expression is still defined in terms of ALT |
48 def OPT(r: Rexp) = ALT(r, ONE) |
49 def OPT(r: Rexp) = ALT(r, ONE) |
49 |
50 |
50 |
51 |
51 // Test Cases |
52 // Test Cases |
52 |
53 |
71 println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i)))) |
72 println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i)))) |
72 } |
73 } |
73 |
74 |
74 |
75 |
75 //test: (a*)* b |
76 //test: (a*)* b |
76 for (i <- 1 to 20) { |
77 for (i <- 1 to 21) { |
77 println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i)))) |
78 println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i)))) |
78 } |
79 } |
79 |
80 |
80 for (i <- 1 to 20) { |
81 for (i <- 1 to 21) { |
81 println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i)))) |
82 println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i)))) |
82 } |
83 } |
83 |
84 |
84 |
85 |
85 |
86 |
93 case STAR(r) => 1 + size(r) |
94 case STAR(r) => 1 + size(r) |
94 case NTIMES(r, _) => 1 + size(r) |
95 case NTIMES(r, _) => 1 + size(r) |
95 } |
96 } |
96 |
97 |
97 // EVIL1(n) has now a constant size, no matter |
98 // EVIL1(n) has now a constant size, no matter |
98 // what n is |
99 // what n is; also the derivative only grows |
|
100 // moderately |
99 |
101 |
100 size(EVIL1(1)) // 7 |
102 size(EVIL1(1)) // 7 |
101 size(EVIL1(3)) // 7 |
103 size(EVIL1(3)) // 7 |
102 size(EVIL1(5)) // 7 |
104 size(EVIL1(5)) // 7 |
103 size(EVIL1(7)) // 7 |
105 size(EVIL1(7)) // 7 |
104 |
106 |
|
107 size(ders("".toList, EVIL1(5))) // 7 |
|
108 size(ders("a".toList, EVIL1(5))) // 16 |
|
109 size(ders("aa".toList, EVIL1(5))) // 35 |
|
110 size(ders("aaa".toList, EVIL1(5))) // 59 |
|
111 size(ders("aaaa".toList, EVIL1(5))) // 88 |
|
112 size(ders("aaaaa".toList, EVIL1(5))) // 122 |
|
113 size(ders("aaaaaa".toList, EVIL1(5))) // 151 |
105 |
114 |
106 // but the size of the derivatives can still grow |
115 // but the size of the derivatives can still grow |
107 // quite dramatically |
116 // quite dramatically in case of EVIL2 |
108 |
117 |
109 size(ders("".toList, EVIL2)) // 5 |
118 size(ders("".toList, EVIL2)) // 5 |
110 size(ders("a".toList, EVIL2)) // 12 |
119 size(ders("a".toList, EVIL2)) // 12 |
111 size(ders("aa".toList, EVIL2)) // 28 |
120 size(ders("aa".toList, EVIL2)) // 28 |
112 size(ders("aaa".toList, EVIL2)) // 58 |
121 size(ders("aaa".toList, EVIL2)) // 58 |
113 size(ders("aaaa".toList, EVIL2)) // 116 |
122 size(ders("aaaa".toList, EVIL2)) // 116 |
|
123 size(ders("aaaaa".toList, EVIL2)) // 230 |
|
124 size(ders("aaaaaa".toList, EVIL2)) // 456 |