190 

   191 def pp(r: Rexp): String = r match {

   192   case SEQ(CHAR(a1), SEQ(r1, r2)) => s"${a1}${pp(r1)}${pp(r2)}"

   193   case SEQ(ONE, SEQ(r1, r2)) => s"1${pp(r1)}${pp(r2)}"

   194   case SEQ(ZERO, SEQ(r1, r2)) => s"0${pp(r1)}${pp(r2)}"

   195   case SEQ(CHAR(a1), CHAR(a2)) => s"${a1}${a2}"

   196   case SEQ(ONE, CHAR(a2)) => s"1${a2}"

   197   case SEQ(ZERO, CHAR(a2)) => s"0${a2}" 

   198   case ZERO => "0"

   199   case ONE => "1"

   200   case CHAR(a) => a.toString

   201   case ALT(r1, r2) => s"(${pp(r1)} + ${pp(r2)})"

   202   case SEQ(r1, r2) => s"(${pp(r1)} o ${pp(r2)})"

   203   case STAR(r1) => s"(${pp(r1)})*"

   204 }

   205 

   206 

   207 val REG = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a'))))

   208 

   209 print(pp(ders("".toList, REG)))

   210 print(pp(ders("a".toList, REG)))

   211 print(pp(ders("aa".toList, REG)))

   212 print(pp(ders("aaa".toList, REG)))

   213 

   214 size(ders("".toList, REG))        // 6

   215 size(ders("a".toList, REG))       // 12

   216 size(ders("aa".toList, REG))      // 27

   217 size(ders("aaa".toList, REG))     // 55

   218 size(ders("aaaa".toList, REG))    // 8

   219 size(ders("aaaaa".toList, REG))   // 169

   220 size(ders("aaaaaa".toList, REG))  // 283

   221 size(ders(("a" * 7).toList, REG)) // 468

   222 size(ders(("a" * 8).toList, REG)) // 767

   223 size(ders(("a" * 9).toList, REG)) // 1251

   224 size(ders(("a" * 10).toList, REG))// 2034

   225 size(ders(("a" * 11).toList, REG))// 3301

   226 

   227 for (i <- (0 to 40)) {

   228   println(s"$i:" + size(ders(("a" * i).toList, REG)))

   229 }