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