--- a/progs/app5.scala	Sat Sep 27 00:37:02 2014 +0100
+++ b/progs/app5.scala	Sun Sep 28 18:07:58 2014 +0100
@@ -6,3 +6,22 @@
   case SEQ(r1, r2) => nullable(r1) && nullable(r2)
   case STAR(_) => true
 }
+
+def der (c: Char, r: Rexp) : Rexp = r match {
+  case NULL => NULL
+  case EMPTY => NULL
+  case CHAR(d) => if (c == d) EMPTY else NULL
+  case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
+  case SEQ(r1, r2) => 
+    if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
+    else SEQ(der(c, r1), r2)
+  case STAR(r) => SEQ(der(c, r), STAR(r))
+}
+
+def ders (s: List[Char], r: Rexp) : Rexp = s match {
+  case Nil => r
+  case c::s => ders(s, der(c, r))
+}
+
+def matches(r: Rexp, s: String) : Boolean = 
+  nullable(ders(s.toList, r))