--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Fahad/Eclipse/ScalaProjects/bin/Handouts/Handout2.sc	Sat Nov 01 20:28:05 2014 +0000
@@ -0,0 +1,118 @@
+package Handouts
+
+import io.Source
+import scala.util.matching.Regex
+import scala.util._
+
+object Handout2 {
+  abstract class Rexp
+  case object NULL extends Rexp
+  case object EMPTY extends Rexp
+  case class CHAR(c: Char) extends Rexp
+  case class ALT(r1: Rexp, r2: Rexp) extends Rexp
+  case class SEQ(r1: Rexp, r2: Rexp) extends Rexp
+  case class STAR(r: Rexp) extends Rexp
+  case class NTIMES(r: Rexp, n: Int) extends Rexp
+
+  def OPT(r: Rexp) = ALT(r, EMPTY)                //> OPT: (r: Handouts.Handout2.Rexp)Handouts.Handout2.ALT
+
+  /*
+  def NTIMES(r: Rexp, n: Int): Rexp = n match {
+    case 0 => EMPTY
+    case 1 => r
+    case n => SEQ(r, NTIMES(r, n - 1))
+  }
+  */
+
+  def nullable(r: Rexp): Boolean = r match {
+    case NULL => false
+    case EMPTY => true
+    case CHAR(_) => false
+    case ALT(r1, r2) => nullable(r1) || nullable(r2)
+    case SEQ(r1, r2) => nullable(r1) && nullable(r2)
+    case STAR(_) => true
+    case NTIMES(r, i) => if (i == 0) true else nullable(r)
+  }                                               //> nullable: (r: Handouts.Handout2.Rexp)Boolean
+
+  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))
+    case NTIMES(r, i) =>
+      if (i == 0) NULL else SEQ(der(c, r), NTIMES(r, i - 1))
+  }                                               //> der: (c: Char, r: Handouts.Handout2.Rexp)Handouts.Handout2.Rexp
+
+  def _ders(s: List[Char], r: Rexp): Rexp = s match {
+    case Nil => r
+    case c :: s => ders(s, der(c, r))
+  }                                               //> _ders: (s: List[Char], r: Handouts.Handout2.Rexp)Handouts.Handout2.Rexp
+
+  def ders(s: List[Char], r: Rexp): Rexp = s match {
+    case Nil => r
+    case c :: s => ders(s, simp(der(c, r)))
+  }                                               //> ders: (s: List[Char], r: Handouts.Handout2.Rexp)Handouts.Handout2.Rexp
+
+  def matches(r: Rexp, s: String): Boolean =
+    nullable(ders(s.toList, r))                   //> matches: (r: Handouts.Handout2.Rexp, s: String)Boolean
+
+  def simp(r: Rexp): Rexp = r match {
+    case ALT(r1, r2) => {
+      val r1s = simp(r1)
+      val r2s = simp(r2)
+      (r1s, r2s) match {
+        case (NULL, _) => r2s
+        case (_, NULL) => r1s
+        case _ => if (r1s == r2s) r1s else ALT(r1s, r2s)
+      }
+    }
+    case SEQ(r1, r2) => {
+      val r1s = simp(r1)
+      val r2s = simp(r2)
+      (r1s, r2s) match {
+        case (NULL, _) => NULL
+        case (_, NULL) => NULL
+        case (EMPTY, _) => r2s
+        case (_, EMPTY) => r1s
+        case _ => SEQ(r1s, r2s)
+      }
+    }
+    case NTIMES(r, n) => NTIMES(simp(r), n)
+    case r => r
+  }                                               //> simp: (r: Handouts.Handout2.Rexp)Handouts.Handout2.Rexp
+
+  /************************************************************************************************************************************/
+  // der test
+  // r = {(a.b) + b}*
+  val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b')))
+                                                  //> r  : Handouts.Handout2.STAR = STAR(ALT(SEQ(CHAR(a),CHAR(b)),CHAR(b)))
+
+  // => [{(_.b) + null} . {(a.b)+b}*]
+  der('a', r)                                     //> res0: Handouts.Handout2.Rexp = SEQ(ALT(SEQ(EMPTY,CHAR(b)),NULL),STAR(ALT(SE
+                                                  //| Q(CHAR(a),CHAR(b)),CHAR(b))))
+  // => [{(null.b) + _} . {(a.b)+b}*]
+  der('b', r)                                     //> res1: Handouts.Handout2.Rexp = SEQ(ALT(SEQ(NULL,CHAR(b)),EMPTY),STAR(ALT(SE
+                                                  //| Q(CHAR(a),CHAR(b)),CHAR(b))))
+  // => [{(null.b) + _} . {(a.b)+b}*]
+  der('c', r)                                     //> res2: Handouts.Handout2.Rexp = SEQ(ALT(SEQ(NULL,CHAR(b)),NULL),STAR(ALT(SEQ
+                                                  //| (CHAR(a),CHAR(b)),CHAR(b))))
+
+  val r2 = ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))
+                                                  //> r2  : Handouts.Handout2.ALT = ALT(SEQ(CHAR(a),CHAR(b)),CHAR(b))
+  der('a', r2)                                    //> res3: Handouts.Handout2.Rexp = ALT(SEQ(EMPTY,CHAR(b)),NULL)
+
+  val r3 = SEQ(CHAR('a'), CHAR('b'))              //> r3  : Handouts.Handout2.SEQ = SEQ(CHAR(a),CHAR(b))
+  der('a', r3)                                    //> res4: Handouts.Handout2.Rexp = SEQ(EMPTY,CHAR(b))
+
+  val r4 = CHAR('a')                              //> r4  : Handouts.Handout2.CHAR = CHAR(a)
+  der('a', r4)                                    //> res5: Handouts.Handout2.Rexp = EMPTY
+
+  nullable(r)                                     //> res6: Boolean = true
+  nullable(r2)                                    //> res7: Boolean = false
+  nullable(r3)                                    //> res8: Boolean = false
+  nullable(r4)                                    //> res9: Boolean = false
+}
\ No newline at end of file