35 def % = STAR(s) |
37 def % = STAR(s) |
36 def ~ (r: Rexp) = SEQ(s, r) |
38 def ~ (r: Rexp) = SEQ(s, r) |
37 def ~ (r: String) = SEQ(s, r) |
39 def ~ (r: String) = SEQ(s, r) |
38 } |
40 } |
39 |
41 |
40 // (1) Complete the function nullable according to |
42 // (5) Complete the function nullable according to |
41 // the definition given in the coursework; this |
43 // the definition given in the coursework; this |
42 // function checks whether a regular expression |
44 // function checks whether a regular expression |
43 // can match the empty string and Returns a boolean |
45 // can match the empty string and Returns a boolean |
44 // accordingly. |
46 // accordingly. |
45 |
47 |
46 //def nullable (r: Rexp) : Boolean = ... |
48 //def nullable (r: Rexp) : Boolean = ... |
47 |
49 |
48 |
50 |
49 // (2) Complete the function der according to |
51 // (6) Complete the function der according to |
50 // the definition given in the coursework; this |
52 // the definition given in the coursework; this |
51 // function calculates the derivative of a |
53 // function calculates the derivative of a |
52 // regular expression w.r.t. a character. |
54 // regular expression w.r.t. a character. |
53 |
55 |
54 //def der (c: Char, r: Rexp) : Rexp = ... |
56 //def der (c: Char, r: Rexp) : Rexp = ... |
55 |
57 |
56 |
58 |
57 // (3) Complete the simp function according to |
59 // (7) Complete the simp function according to |
58 // the specification given in the coursework; this |
60 // the specification given in the coursework; this |
59 // function simplifies a regular expression from |
61 // function simplifies a regular expression from |
60 // the inside out, like you would simplify arithmetic |
62 // the inside out, like you would simplify arithmetic |
61 // expressions; however it does not simplify inside |
63 // expressions; however it does not simplify inside |
62 // STAR-regular expressions. |
64 // STAR-regular expressions. |
63 |
65 |
64 //def simp(r: Rexp) : Rexp = ... |
66 //def simp(r: Rexp) : Rexp = ... |
65 |
67 |
66 |
68 |
67 // (4) Complete the two functions below; the first |
69 // (8) Complete the two functions below; the first |
68 // calculates the derivative w.r.t. a string; the second |
70 // calculates the derivative w.r.t. a string; the second |
69 // is the regular expression matcher taking a regular |
71 // is the regular expression matcher taking a regular |
70 // expression and a string and checks whether the |
72 // expression and a string and checks whether the |
71 // string matches the regular expression |
73 // string matches the regular expression |
72 |
74 |
73 //def ders (s: List[Char], r: Rexp) : Rexp = ... |
75 //def ders (s: List[Char], r: Rexp) : Rexp = ... |
74 |
76 |
75 //def matcher(r: Rexp, s: String): Boolean = ... |
77 //def matcher(r: Rexp, s: String): Boolean = ... |
76 |
78 |
77 |
79 |
78 // (5) Complete the size function for regular |
80 // (9) Complete the size function for regular |
79 // expressions according to the specification |
81 // expressions according to the specification |
80 // given in the coursework. |
82 // given in the coursework. |
81 |
83 |
82 //def size(r: Rexp): Int = ... |
84 //def size(r: Rexp): Int = ... |
83 |
85 |