Binary file handouts/ho04.pdf has changed

--- a/handouts/ho04.tex	Fri Oct 09 14:48:06 2015 +0100
+++ b/handouts/ho04.tex	Fri Oct 16 08:42:21 2015 +0100
@@ -90,7 +90,7 @@
 \pcode{Empty}.
  
  {\small\lstinputlisting[language=Scala,numbers=none]
-{../progs/app03.scala}}
+{../progs/app01.scala}}
 
  
 {\small\lstinputlisting[language=Scala,numbers=none]

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/token-bak.scala	Fri Oct 16 08:42:21 2015 +0100
@@ -0,0 +1,145 @@
+import scala.language.implicitConversions
+import scala.language.reflectiveCalls
+import scala.util._
+import scala.annotation.tailrec
+
+sealed 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
+
+def charlist2rexp(s : List[Char]) : Rexp = s match {
+  case Nil => EMPTY
+  case c::Nil => CHAR(c)
+  case c::s => SEQ(CHAR(c), charlist2rexp(s))
+}
+implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList)
+
+
+implicit def RexpOps(r: Rexp) = new {
+  def | (s: Rexp) = ALT(r, s)
+  def % = STAR(r)
+  def ~ (s: Rexp) = SEQ(r, s)
+}
+
+implicit def stringOps(s: String) = new {
+  def | (r: Rexp) = ALT(s, r)
+  def | (r: String) = ALT(s, r)
+  def % = STAR(s)
+  def ~ (r: Rexp) = SEQ(s, r)
+  def ~ (r: String) = SEQ(s, r)
+}
+
+def Range(s : List[Char]) : Rexp = s match {
+  case Nil => NULL
+  case c::Nil => CHAR(c)
+  case c::s => ALT(CHAR(c), Range(s))
+}
+def RANGE(s: String) = Range(s.toList)
+
+def PLUS(r: Rexp) = SEQ(r, STAR(r))
+
+val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_")
+val DIGIT = RANGE("0123456789")
+val ID = SYM ~ (SYM | DIGIT).% 
+val NUM = PLUS(DIGIT)
+val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" 
+val SEMI: Rexp = ";"
+val OP: Rexp = ":=" | "=" | "-" | "+" | "*" | "!=" | "<" | ">"
+val WHITESPACE = PLUS(RANGE(" \n"))
+val RPAREN: Rexp = ")"
+val LPAREN: Rexp = "("
+val BEGIN: Rexp = "{"
+val END: Rexp = "}"
+
+//regular expressions ranked by position in the list
+val regs: List[Rexp] = 
+  List(KEYWORD, ID, OP, NUM, SEMI, LPAREN, RPAREN, BEGIN, END, WHITESPACE)
+
+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
+}
+
+def zeroable (r: Rexp) : Boolean = r match {
+  case NULL => true
+  case EMPTY => false
+  case CHAR(_) => false
+  case ALT(r1, r2) => zeroable(r1) && zeroable(r2)
+  case SEQ(r1, r2) => zeroable(r1) || zeroable(r2)
+  case STAR(_) => false
+}
+
+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))
+}
+
+
+// calculates derivatives until all of them are zeroable
+@tailrec
+def munch(s: List[Char], 
+          pos: Int, 
+          rs: List[Rexp], 
+          last: Option[Int]): Option[Int] = rs match {
+  case Nil => last
+  case rs if (s.length <= pos) => last
+  case rs => {
+    val ders = rs.map(der(s(pos), _))
+    val rs_nzero = ders.filterNot(zeroable(_))
+    val rs_nulls = ders.filter(nullable(_))
+    val new_last = if (rs_nulls != Nil) Some(pos) else last
+    munch(s, 1 + pos, rs_nzero, new_last)
+  }
+}
+
+// iterates the munching function and prints 
+// out the component strings
+@tailrec
+def tokenize(s: String, rs: List[Rexp]) : Unit = munch(s.toList, 0, rs, None) match {
+  case None if (s == "") => println("EOF")
+  case None => println(s"Lexing error: $s")
+  case Some(n) => {
+    val (head, tail) = s.splitAt(n + 1)
+    print(s"|${head.replaceAll("\n","RET")}|")
+    tokenize(tail, rs)
+  }
+}
+
+
+val test_prog = """
+start := XXX;
+x := start;
+y := start;
+z := start;
+while 0 < x do {
+ while 0 < y do {
+  while 0 < z do {
+    z := z - 1
+  };
+  z := start;
+  y := y - 1
+ };     
+ y := start;
+ x := x - 1
+};
+write x;
+write y;
+write z
+"""
+
+tokenize(test_prog, regs)

--- a/progs/token.scala	Fri Oct 09 14:48:06 2015 +0100
+++ b/progs/token.scala	Fri Oct 16 08:42:21 2015 +0100
@@ -1,25 +1,33 @@
-import scala.language.implicitConversions
+import scala.language.implicitConversions    
 import scala.language.reflectiveCalls
-import scala.util._
-import scala.annotation.tailrec
+import scala.annotation.tailrec   
 
-sealed abstract class Rexp
-
+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 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 RECD(x: String, r: Rexp) extends Rexp
 
-def charlist2rexp(s : List[Char]) : Rexp = s match {
+abstract class Val
+case object Void extends Val
+case class Chr(c: Char) extends Val
+case class Sequ(v1: Val, v2: Val) extends Val
+case class Left(v: Val) extends Val
+case class Right(v: Val) extends Val
+case class Stars(vs: List[Val]) extends Val
+case class Rec(x: String, v: Val) extends Val
+   
+// some convenience for typing in regular expressions
+def charlist2rexp(s : List[Char]): Rexp = s match {
   case Nil => EMPTY
   case c::Nil => CHAR(c)
   case c::s => SEQ(CHAR(c), charlist2rexp(s))
 }
 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList)
 
-
 implicit def RexpOps(r: Rexp) = new {
   def | (s: Rexp) = ALT(r, s)
   def % = STAR(r)
@@ -32,34 +40,11 @@
   def % = STAR(s)
   def ~ (r: Rexp) = SEQ(s, r)
   def ~ (r: String) = SEQ(s, r)
+  def $ (r: Rexp) = RECD(s, r)
 }
 
-def Range(s : List[Char]) : Rexp = s match {
-  case Nil => NULL
-  case c::Nil => CHAR(c)
-  case c::s => ALT(CHAR(c), Range(s))
-}
-def RANGE(s: String) = Range(s.toList)
-
-def PLUS(r: Rexp) = SEQ(r, STAR(r))
-
-val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_")
-val DIGIT = RANGE("0123456789")
-val ID = SYM ~ (SYM | DIGIT).% 
-val NUM = PLUS(DIGIT)
-val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" 
-val SEMI: Rexp = ";"
-val OP: Rexp = ":=" | "=" | "-" | "+" | "*" | "!=" | "<" | ">"
-val WHITESPACE = PLUS(RANGE(" \n"))
-val RPAREN: Rexp = ")"
-val LPAREN: Rexp = "("
-val BEGIN: Rexp = "{"
-val END: Rexp = "}"
-
-//regular expressions ranked by position in the list
-val regs: List[Rexp] = 
-  List(KEYWORD, ID, OP, NUM, SEMI, LPAREN, RPAREN, BEGIN, END, WHITESPACE)
-
+// nullable function: tests whether the regular 
+// expression can recognise the empty string
 def nullable (r: Rexp) : Boolean = r match {
   case NULL => false
   case EMPTY => true
@@ -67,79 +52,224 @@
   case ALT(r1, r2) => nullable(r1) || nullable(r2)
   case SEQ(r1, r2) => nullable(r1) && nullable(r2)
   case STAR(_) => true
+  case RECD(_, r1) => nullable(r1)
 }
 
-def zeroable (r: Rexp) : Boolean = r match {
-  case NULL => true
-  case EMPTY => false
-  case CHAR(_) => false
-  case ALT(r1, r2) => zeroable(r1) && zeroable(r2)
-  case SEQ(r1, r2) => zeroable(r1) || zeroable(r2)
-  case STAR(_) => false
-}
-
+// derivative of a regular expression w.r.t. a character
 def der (c: Char, r: Rexp) : Rexp = r match {
   case NULL => NULL
-  case EMPTY => 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 RECD(_, r1) => der(c, r1)
+}
+
+// derivative w.r.t. a string (iterates der)
+def ders (s: List[Char], r: Rexp) : Rexp = s match {
+  case Nil => r
+  case c::s => ders(s, der(c, r))
+}
+
+// extracts a string from value
+def flatten(v: Val) : String = v match {
+  case Void => ""
+  case Chr(c) => c.toString
+  case Left(v) => flatten(v)
+  case Right(v) => flatten(v)
+  case Sequ(v1, v2) => flatten(v1) + flatten(v2)
+  case Stars(vs) => vs.map(flatten).mkString
+  case Rec(_, v) => flatten(v)
+}
+
+// extracts an environment from a value
+def env(v: Val) : List[(String, String)] = v match {
+  case Void => Nil
+  case Chr(c) => Nil
+  case Left(v) => env(v)
+  case Right(v) => env(v)
+  case Sequ(v1, v2) => env(v1) ::: env(v2)
+  case Stars(vs) => vs.flatMap(env)
+  case Rec(x, v) => (x, flatten(v))::env(v)
+}
+
+// injection part
+def mkeps(r: Rexp) : Val = r match {
+  case EMPTY => Void
+  case ALT(r1, r2) => 
+    if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))
+  case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
+  case STAR(r) => Stars(Nil)
+  case RECD(x, r) => Rec(x, mkeps(r))
 }
 
 
-// calculates derivatives until all of them are zeroable
-@tailrec
-def munch(s: List[Char], 
-          pos: Int, 
-          rs: List[Rexp], 
-          last: Option[Int]): Option[Int] = rs match {
-  case Nil => last
-  case rs if (s.length <= pos) => last
-  case rs => {
-    val ders = rs.map(der(s(pos), _))
-    val rs_nzero = ders.filterNot(zeroable(_))
-    val rs_nulls = ders.filter(nullable(_))
-    val new_last = if (rs_nulls != Nil) Some(pos) else last
-    munch(s, 1 + pos, rs_nzero, new_last)
+def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
+  case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
+  case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)
+  case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)
+  case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))
+  case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
+  case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
+  case (CHAR(d), Void) => Chr(c) 
+  case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
+}
+
+// main lexing function (produces a value)
+def lex(r: Rexp, s: List[Char]) : Val = s match {
+  case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched")
+  case c::cs => inj(r, c, lex(der(c, r), cs))
+}
+
+def lexing(r: Rexp, s: String) : Val = lex(r, s.toList)
+
+// some "rectification" functions for simplification
+def F_ID(v: Val): Val = v
+def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v))
+def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v))
+def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
+  case Right(v) => Right(f2(v))
+  case Left(v) => Left(f1(v))
+}
+def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
+  case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))
+}
+def F_SEQ_Void1(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(Void), f2(v))
+def F_SEQ_Void2(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(v), f2(Void))
+def F_RECD(f: Val => Val) = (v:Val) => v match {
+  case Rec(x, v) => Rec(x, f(v))
+}
+def F_ERROR(v: Val): Val = throw new Exception("error")
+
+// simplification of regular expressions returning also an
+// rectification function; no simplification under STAR 
+def simp(r: Rexp): (Rexp, Val => Val) = r match {
+  case ALT(r1, r2) => {
+    val (r1s, f1s) = simp(r1)
+    val (r2s, f2s) = simp(r2)
+    (r1s, r2s) match {
+      case (NULL, _) => (r2s, F_RIGHT(f2s))
+      case (_, NULL) => (r1s, F_LEFT(f1s))
+      case _ => if (r1s == r2s) (r1s, F_LEFT(f1s))
+                else (ALT (r1s, r2s), F_ALT(f1s, f2s)) 
+    }
+  }
+  case SEQ(r1, r2) => {
+    val (r1s, f1s) = simp(r1)
+    val (r2s, f2s) = simp(r2)
+    (r1s, r2s) match {
+      case (NULL, _) => (NULL, F_ERROR)
+      case (_, NULL) => (NULL, F_ERROR)
+      case (EMPTY, _) => (r2s, F_SEQ_Void1(f1s, f2s))
+      case (_, EMPTY) => (r1s, F_SEQ_Void2(f1s, f2s))
+      case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s))
+    }
+  }
+  case RECD(x, r1) => {
+    val (r1s, f1s) = simp(r1)
+    (RECD(x, r1s), F_RECD(f1s))
+  }
+  case r => (r, F_ID)
+}
+
+def lex_simp(r: Rexp, s: List[Char]) : Val = s match {
+  case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched")
+  case c::cs => {
+    val (r_simp, f_simp) = simp(der(c, r))
+    inj(r, c, f_simp(lex_simp(r_simp, cs)))
   }
 }
 
-// iterates the munching function and prints 
-// out the component strings
-@tailrec
-def tokenize(s: String, rs: List[Rexp]) : Unit = munch(s.toList, 0, rs, None) match {
-  case None if (s == "") => println("EOF")
-  case None => println(s"Lexing error: $s")
-  case Some(n) => {
-    val (head, tail) = s.splitAt(n + 1)
-    print(s"|${head.replaceAll("\n","RET")}|")
-    tokenize(tail, rs)
-  }
+def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList)
+
+lexing_simp(("a" + "ab") | ("b" + ""), "ab")
+
+// Lexing Rules for a Small While Language
+
+def PLUS(r: Rexp) = r ~ r.%
+val SYM = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
+val DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
+val ID = SYM ~ (SYM | DIGIT).% 
+val NUM = PLUS(DIGIT)
+val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" | "true" | "false"
+val SEMI: Rexp = ";"
+val OP: Rexp = ":=" | "==" | "-" | "+" | "*" | "!=" | "<" | ">" | "<=" | ">=" | "%" | "/"
+val WHITESPACE = PLUS(" " | "\n" | "\t")
+val RPAREN: Rexp = ")"
+val LPAREN: Rexp = "("
+val BEGIN: Rexp = "{"
+val END: Rexp = "}"
+val STRING: Rexp = "\"" ~ SYM.% ~ "\""
+
+
+val WHILE_REGS = (("k" $ KEYWORD) | 
+                  ("i" $ ID) | 
+                  ("o" $ OP) | 
+                  ("n" $ NUM) | 
+                  ("s" $ SEMI) | 
+                  ("str" $ STRING) |
+                  ("p" $ (LPAREN | RPAREN)) | 
+                  ("b" $ (BEGIN | END)) | 
+                  ("w" $ WHITESPACE)).%
+
+//   Testing
+//============
+
+def time[T](code: => T) = {
+  val start = System.nanoTime()
+  val result = code
+  val end = System.nanoTime()
+  println((end - start)/1.0e9)
+  result
+}
+
+val r1 = ("a" | "ab") ~ ("bcd" | "c")
+println(lexing(r1, "abcd"))
+
+val r2 = ("" | "a") ~ ("ab" | "b")
+println(lexing(r2, "ab"))
+
+
+// Two Simple While Tests
+//========================
+println("prog0 test")
+
+val prog0 = """read n"""
+println(env(lexing_simp(WHILE_REGS, prog0)))
+
+println("prog1 test")
+
+val prog1 = """read  n; write (n)"""
+println(env(lexing_simp(WHILE_REGS, prog1)))
+
+
+// Big Test
+//==========
+
+val prog2 = """
+write "fib";
+read n;
+minus1 := 0;
+minus2 := 1;
+while n > 0 do {
+  temp := minus2;
+  minus2 := minus1 + minus2;
+  minus1 := temp;
+  n := n - 1
+};
+write "result";
+write minus2
+"""
+
+println("Tokens")
+println(env(lexing_simp(WHILE_REGS, prog2)))
+
+for (i <- 1 to 80) {
+  print(i.toString + ":  ")
+  time(lexing_simp(WHILE_REGS, prog2 * i))
 }
 
 
-val test_prog = """
-start := XXX;
-x := start;
-y := start;
-z := start;
-while 0 < x do {
- while 0 < y do {
-  while 0 < z do {
-    z := z - 1
-  };
-  z := start;
-  y := y - 1
- };     
- y := start;
- x := x - 1
-};
-write x;
-write y;
-write z
-"""
-
-tokenize(test_prog, regs)

Binary file slides/slides03.pdf has changed

Binary file slides/slides04.pdf has changed

--- a/slides/slides04.tex	Fri Oct 09 14:48:06 2015 +0100
+++ b/slides/slides04.tex	Fri Oct 16 08:42:21 2015 +0100
@@ -49,7 +49,9 @@
 \path[->,red, line width=2mm] (nfa) edge node [above=4mm, black] 
      {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa);
 \path[->, red, line width=2mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa);
-\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp);
+%%\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp);
+\path[->, red, line width=2mm] (dfa) edge [bend left=45] node [below, black] {\begin{tabular}{l}Brzozowski's\\ method\end{tabular}} (rexp);
+
 \end{tikzpicture}\\
 \end{center}
 
@@ -58,9 +60,8 @@
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[t]
-\frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}}
+\frametitle{\bl{$a^?^{\{n\}} \cdot a^{\{n\}}$}}
 
 \begin{tikzpicture}
 \begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs},
@@ -85,10 +86,9 @@
 \end{axis}
 \end{tikzpicture}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{DFA to Rexp}
@@ -118,18 +118,16 @@
 \end{tabular}
 \end{center}
 
-\onslide<2->{
 Arden's Lemma:
 \begin{center}
 If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
 \end{center}
-}
+
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 \frametitle{DFA Minimisation}
 
@@ -145,65 +143,6 @@
 \item All unmarked pairs can be merged.
 \end{enumerate}
 
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-
-\begin{center}
-\begin{tikzpicture}[>=stealth',very thick,auto,
-                             every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]
-\node[state,initial]  (q_0)  {$q_0$};
-\node[state] (q_1) [right=of q_0] {$q_1$};
-\node[state] (q_2) [below right=of q_0] {$q_2$};
-\node[state] (q_3) [right=of q_2] {$q_3$};
-\node[state, accepting] (q_4) [right=of q_1] {$q_4$};
-\path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);
-\path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);
-\path[->] (q_4) edge [loop right] node  {\alert{$a, b$}} ();
-\path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);
-\path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);
-\path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);
-\path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);
-\path[->] (q_2) edge [loop left] node  {\alert{$b$}} ();
-\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);
-\end{tikzpicture}
-\end{center}
-
-\mbox{}\\[-20mm]\mbox{}
-
-\begin{center}
-\begin{tikzpicture}[scale=0.8,line width=0.8mm]
-\draw (0,0) -- (4,0);
-\draw (0,1) -- (4,1);
-\draw (0,2) -- (3,2);
-\draw (0,3) -- (2,3);
-\draw (0,4) -- (1,4);
-
-\draw (0,0) -- (0, 4);
-\draw (1,0) -- (1, 4);
-\draw (2,0) -- (2, 3);
-\draw (3,0) -- (3, 2);
-\draw (4,0) -- (4, 1);
-
-\draw (0.5,-0.5) node {$q_0$}; 
-\draw (1.5,-0.5) node {$q_1$}; 
-\draw (2.5,-0.5) node {$q_2$}; 
-\draw (3.5,-0.5) node {$q_3$};
- 
-\draw (-0.5, 3.5) node {$q_1$}; 
-\draw (-0.5, 2.5) node {$q_2$}; 
-\draw (-0.5, 1.5) node {$q_3$}; 
-\draw (-0.5, 0.5) node {$q_4$}; 
-
-\draw (0.5,0.5) node {\large$\star$}; 
-\draw (1.5,0.5) node {\large$\star$}; 
-\draw (2.5,0.5) node {\large$\star$}; 
-\draw (3.5,0.5) node {\large$\star$};
-\end{tikzpicture}
-\end{center}
-
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
@@ -288,56 +227,6 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Alternatives}
-\mbox{}\\[-17mm]\mbox{}
-
-\begin{center}
-\begin{tikzpicture}[>=stealth',very thick,auto,
-                    every state/.style={minimum size=0pt,
-                    inner sep=2pt,draw=blue!50,very thick,fill=blue!20}]
-\only<1>{\node[state,initial]  (q_0)  {$q_0$};}
-\only<2->{\node[state,accepting]  (q_0)  {$q_0$};}
-\node[state] (q_1) [right=of q_0] {$q_1$};
-\node[state] (q_2) [below right=of q_0] {$q_2$};
-\node[state] (q_3) [right=of q_2] {$q_3$};
-\only<1>{\node[state, accepting] (q_4) [right=of q_1] {$q_4$};}
-\only<2->{\node[state, initial right] (q_4) [right=of q_1] {$q_4$};}
-\only<1-2>{
-\path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);
-\path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);
-\path[->] (q_4) edge [loop above] node  {\alert{$a, b$}} ();
-\path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);
-\path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);
-\path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);
-\path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);
-\path[->] (q_2) edge [loop left] node  {\alert{$b$}} ();
-\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);}
-\only<3->{
-\path[<-] (q_0) edge node [above]  {\alert{$a$}} (q_1);
-\path[<-] (q_1) edge node [above]  {\alert{$a$}} (q_4);
-\path[<-] (q_4) edge [loop above] node  {\alert{$a, b$}} ();
-\path[<-] (q_3) edge node [right]  {\alert{$a$}} (q_4);
-\path[<-] (q_2) edge node [above]  {\alert{$a$}} (q_3);
-\path[<-] (q_1) edge node [right]  {\alert{$b$}} (q_2);
-\path[<-] (q_0) edge node [above]  {\alert{$b$}} (q_2);
-\path[<-] (q_2) edge [loop left] node  {\alert{$b$}} ();
-\path[<-] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);}
-\end{tikzpicture}
-\end{center}
-\mbox{}\\[-18mm]
-
-\begin{itemize}
-\item<2-> exchange initial / accepting states
-\item<3-> reverse all edges
-\item<4-> subset construction $\Rightarrow$ DFA
-\item<5-> repeat once more \onslide<6->{$\Rightarrow$ minimal DFA}
-\end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
 \frametitle{Regular Languages}
 
 Two equivalent definitions:\bigskip
@@ -382,13 +271,77 @@
 \end{tikzpicture}
 \end{center}\bigskip\bigskip
 
-\onslide<2>{But requires that the automaton is \alert{completed}!}
+But requires that the automaton is \alert{completed}!
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
+\frametitle{The Goal of this Course}
+\mbox{}\\[-26mm]\mbox{}
+
+\begin{center}
+  \begin{tikzpicture}[scale=1,
+                      node/.style={
+                      rectangle,rounded corners=3mm,
+                      very thick,draw=black!50,
+                      minimum height=18mm, minimum width=20mm,
+                      top color=white,bottom color=black!20}]
+
+  \node at (3.05, 1.8) {\Large\bf Write A Compiler};
+
+  \node (0) at (-2.3,0) {}; 
+  
+  \node (A) at (0,0)  [node] {};
+  \node [below right] at (A.north west) {lexer};
+
+  \node (B) at (3,0)  [node] {};
+  \node [below right=1mm] at (B.north west) 
+    {\mbox{}\hspace{-1mm}parser};
+
+  \node (C) at (6,0)  [node] {};
+  \node [below right] at (C.north west) 
+    {\mbox{}\hspace{-1mm}code gen};
+
+  \node (1) at (8.4,0) {}; 
+
+  \draw [->,line width=4mm] (0) -- (A); 
+  \draw [->,line width=4mm] (A) -- (B); 
+  \draw [->,line width=4mm] (B) -- (C); 
+  \draw [->,line width=4mm] (C) -- (1); 
+  \end{tikzpicture}
+  \end{center}
+  
+Today a lexer.  
+  
+\end{frame}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Survey: Thanks!}
+\small
+
+\begin{itemize}
+\item {\bf My Voice} ``lecturer speaks in a low voice and 
+  is hard to hear him'' ``please use mic'' ``please use mic 
+  \& lecture recording''
+\item {\bf Pace} ``faster pace'' ``a bit quick for me 
+personally''
+\item {\bf Recording} ``please use recording class''
+\item {\bf Module Name} ``misleading''
+\item {\bf Examples} ``more examples''
+\item {\bf Assessment} ``really appreciate extension of 
+  first coursework'' 
+\end{itemize}
+  
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Lexing}
 
 \mbox{\lstinputlisting[language=While]{../progs/fib.while}}
 
@@ -405,29 +358,6 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{A Compiler}
-
-\begin{tikzpicture}[scale=1]
-  \draw[line width=1mm] (-0.3, 0) rectangle (1.5,2);
-  \draw[line width=1mm] (-1.8, 0) rectangle (-3.6,2);
-  \draw (4.4,1) node {Code Gen};
-  \draw (0.6,1.7) node {\small Parser};
-  \draw (-2.7,1.7) node {\small Lexer};
-  
-  \draw[red,->,line width = 2mm] (1.7,1) -- (3.2,1);
-  \draw[red,<-,line width = 2mm] (-0.6,1) -- (-1.6,1);
-  \draw[red,<-,line width = 2mm] (-3.8,1) -- (-4.8,1);
-
-  \draw (-4.6,1.7) node {\small string};
-  \draw (-1.1,1.7) node {\small tokens};
-  \draw ( 2.3,1.7) node {\small AST};
-\end{tikzpicture}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
 
 \tt
@@ -518,6 +448,19 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 
+\begin{frame}[c]
+
+The same problem with\medskip
+
+\[
+\bl{(ab + a) \cdot (c + bc)}
+\]\bigskip
+
+and the string $\bl{abc}$
+
+\end{frame}
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{POSIX: Two Rules}
@@ -616,6 +559,17 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+\begin{frame}[c]
+\small
+
+{\small\lstinputlisting[language=Scala,numbers=none,
+xleftmargin=-5mm] {../progs/app01.scala}}
+
+{\small\lstinputlisting[language=Scala,numbers=none,
+xleftmargin=-5mm] {../progs/app02.scala}}
+
+\end{frame}
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{Mkeps}
@@ -659,6 +613,153 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{textblock}{10}(3,5)
+\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
+\node (r1)  {\bl{$r_1$}};
+\node (r2) [right=of r1] {\bl{$r_2$}};
+\draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
+\node (r3) [right=of r2] {\bl{$r_3$}};
+\draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
+\node (r4) [right=of r3] {\bl{$r_4$}};
+\draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
+\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
+\node (v4) [below=of r4] {\bl{$v_4$}};
+\draw[->,line width=1mm]  (r4) -- (v4);
+\node (v3) [left=of v4] {\bl{$v_3$}};
+\draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
+\node (v2) [left=of v3] {\bl{$v_2$}};
+\draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
+\node (v1) [left=of v2] {\bl{$v_1$}};
+\draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
+\draw[->,line width=0.5mm]  (r3) -- (v3);
+\draw[->,line width=0.5mm]  (r2) -- (v2);
+\draw[->,line width=0.5mm]  (r1) -- (v1);
+\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
+\end{tikzpicture}
+\end{textblock}
+
+\only<2->{
+\begin{textblock}{6}(1,0.8)
+\begin{bubble}[6cm]
+\small
+\begin{tabular}{ll}
+\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
+\bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\
+\bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\
+\bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<2->{
+\begin{textblock}{6}(5,11.4)
+\begin{bubble}[7.6cm]
+\small
+\begin{tabular}{ll}
+\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\
+\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\
+\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\
+\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Flatten}
+
+Obtaining the string underlying a value:
+
+\begin{center}
+\begin{tabular}{lcl}
+  \bl{$|Empty|$}     & \bl{$\dn$} & \bl{$[]$}\\
+  \bl{$|Char(c)|$}   & \bl{$\dn$} & \bl{$[c]$}\\
+  \bl{$|Left(v)|$}   & \bl{$\dn$} & \bl{$|v|$}\\
+  \bl{$|Right(v)|$}  & \bl{$\dn$} & \bl{$|v|$}\\
+  \bl{$|Seq(v_1,v_2)|$}& \bl{$\dn$} & \bl{$|v_1| \,@\, |v_2|$}\\
+  \bl{$|[v_1,\ldots ,v_n]|$} & \bl{$\dn$} & \bl{$|v_1| \,@\ldots @\, |v_n|$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{textblock}{10}(3,5)
+\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
+\node (r1)  {\bl{$r_1$}};
+\node (r2) [right=of r1] {\bl{$r_2$}};
+\draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
+\node (r3) [right=of r2] {\bl{$r_3$}};
+\draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
+\node (r4) [right=of r3] {\bl{$r_4$}};
+\draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
+\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
+\node (v4) [below=of r4] {\bl{$v_4$}};
+\draw[->,line width=1mm]  (r4) -- (v4);
+\node (v3) [left=of v4] {\bl{$v_3$}};
+\draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
+\node (v2) [left=of v3] {\bl{$v_2$}};
+\draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
+\node (v1) [left=of v2] {\bl{$v_1$}};
+\draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
+\draw[->,line width=0.5mm]  (r3) -- (v3);
+\draw[->,line width=0.5mm]  (r2) -- (v2);
+\draw[->,line width=0.5mm]  (r1) -- (v1);
+\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
+\end{tikzpicture}
+\end{textblock}
+
+\begin{textblock}{6}(1,0.8)
+\begin{bubble}[6cm]
+\small
+\begin{tabular}{ll}
+\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
+\bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\
+\bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\
+\bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}
+
+\begin{textblock}{6}(1,11.4)
+\begin{bubble}[7.6cm]
+\small
+\begin{tabular}{ll}
+\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\
+\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\
+\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\
+\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}
+
+\begin{textblock}{6}(12,11.4)
+\begin{bubble}[2cm]
+\small
+\begin{tabular}{ll}
+\bl{$|v_1|$}: & \bl{$abc$}\\
+\bl{$|v_2|$}: & \bl{$bc$}\\
+\bl{$|v_3|$}: & \bl{$c$}\\
+\bl{$|v_4|$}: & \bl{$[]$}
+\end{tabular}
+\end{bubble}
+\end{textblock}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{Lexing}
@@ -719,6 +820,57 @@
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Records}
+
+\begin{itemize}
+\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause
+
+\item \bl{$nullable(x:r) \dn nullable(r)$}
+\item \bl{$der\,c\,(x:r) \dn (x:der\,c\,r)$}
+\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$}
+\item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$}
+\end{itemize}\bigskip\bigskip\pause
+
+\small
+for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{itemize}
+\item Regular expression for email addresses
+
+\begin{center}
+\begin{tabular}{l}
+(name: \bl{$[a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+$})\bl{$\cdot @\cdot$}\\ 
+\qquad(domain: \bl{$[a\mbox{-}z0\mbox{-}9\,.-]^+$}) \bl{$\cdot .\cdot$}\\ 
+\qquad\qquad(top\_level: \bl{$[a\mbox{-}z\,.]^{\{2,6\}}$})
+\end{tabular}
+\end{center}
+
+\bl{\[
+\texttt{christian.urban@kcl.ac.uk}
+\]}
+
+\item result environment:
+
+\begin{center}
+\begin{tabular}{l}
+\bl{$[(name:\texttt{christian.urban}),$}\\ 
+\bl{$\phantom{[}(domain:\texttt{kcl}),$}\\ 
+\bl{$\phantom{[}(top\_level:\texttt{ac.uk})]$}
+\end{tabular}
+\end{center}
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
@@ -740,6 +892,8 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
 
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{Simplification}
@@ -775,6 +929,11 @@
 \end{tikzpicture}
 \end{center}
 
+\small
+\hspace{4.5cm}\bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}
+$\mapsto$
+\bl{$\epsilon$}
+
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
 
@@ -803,6 +962,94 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Rectification}
+
+\begin{center}
+\begin{tabular}{l}
+\bl{$simp(r)$}:\\
+\quad case \bl{$r = r_1 + r_2$}\\
+\qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\
+\qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\
+\qquad case \bl{$r_{1s} = \varnothing$}: 
+       return \bl{$(r_{2s}, \lambda v. \,Right(f_{2s}(v)))$}\\
+\qquad case \bl{$r_{2s} = \varnothing$}: 
+       return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\
+\qquad case \bl{$r_{1s} = r_{2s}$}:
+       return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\
+\qquad otherwise: 
+       return \bl{$(r_{1s} + r_{2s}, f_{alt}(f_{1s}, f_{2s}))$}\\
+\end{tabular}
+\end{center}
+
+\small
+\begin{center}
+\begin{tabular}{l@{\hspace{1mm}}l}
+\bl{$f_{alt}(f_1, f_2) \dn$}\\
+\qquad \bl{$\lambda v.\,$} case \bl{$v = Left(v')$}: 
+      & return \bl{$Left(f_1(v'))$}\\
+\qquad \phantom{$\lambda v.\,$} case \bl{$v = Right(v')$}: 
+      & return \bl{$Right(f_2(v'))$}\\      
+\end{tabular}
+\end{center}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+\begin{frame}[c]
+
+{\footnotesize\lstinputlisting[language=Scala,numbers=none,
+xleftmargin=-5mm] {../progs/app05.scala}}
+
+\end{frame}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Rectification}
+
+\begin{center}
+\begin{tabular}{@{\hspace{-3mm}}l}
+\bl{$simp(r)$}:\ldots\\
+\quad case \bl{$r = r_1 \cdot r_2$}\\
+\qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\
+\qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\
+\qquad case \bl{$r_{1s} = \varnothing$}: 
+       return \bl{$(\varnothing, f_{error})$}\\
+\qquad case \bl{$r_{2s} = \varnothing$}: 
+       return \bl{$(\varnothing, f_{error})$}\\
+\qquad case \bl{$r_{1s} = \epsilon$}: 
+return \bl{$(r_{2s}, \lambda v. \,Seq(f_{1s}(Empty), f_{2s}(v)))$}\\
+\qquad case \bl{$r_{2s} = \epsilon$}: 
+return \bl{$(r_{1s}, \lambda v. \,Seq(f_{1s}(v), f_{2s}(Empty)))$}\\
+\qquad otherwise: 
+       return \bl{$(r_{1s} \cdot r_{2s}, f_{seq}(f_{1s}, f_{2s}))$}\\
+\end{tabular}
+\end{center}
+
+\small
+\begin{center}
+\begin{tabular}{l@{\hspace{1mm}}l}
+\bl{$f_{seq}(f_1, f_2) \dn$}\\
+\qquad \bl{$\lambda v.\,$ case $v = Seq(v_1, v_2)$}: 
+      & return \bl{$Seq(f_1(v_1), f_2(v_2))$}\\
+\end{tabular}
+\end{center}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+
+
+\begin{frame}[c]
+
+{\footnotesize\lstinputlisting[language=Scala,numbers=none,
+xleftmargin=-5mm] {../progs/app06.scala}}
+
+\end{frame}
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{Lexing with Simplification}
@@ -844,6 +1091,29 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+$zeroable(\varnothing)$      & $\dn$ & $true$\\
+$zeroable(\epsilon)$           & $\dn$ &  $f\!alse$\\
+$zeroable (c)$                    & $\dn$ &  $f\!alse$\\
+$zeroable (r_1 + r_2)$        & $\dn$ &  $zeroable(r_1) \wedge zeroable(r_2)$ \\ 
+$zeroable (r_1 \cdot r_2)$  & $\dn$ &  $zeroable(r_1) \vee zeroable(r_2)$ \\
+$zeroable (r^*)$                  & $\dn$ & $f\!alse$\\
+\end{tabular}
+\end{center}
+
+\begin{center}
+$zeroable(r)$ if and only if $L(r) = \varnothing$
+\end{center}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
 \end{document}
 
 %%% Local Variables: