--- a/progs/thompson.scala	Tue Apr 25 12:33:16 2017 +0100
+++ b/progs/thompson.scala	Fri Apr 28 11:01:25 2017 +0100
@@ -1,51 +1,157 @@
-// eNFA that does not accept any string
-def eNFA_ZERO(): NFA[TState, Char] = {
+// Thompson Construction
+// (needs  :load nfa.scala
+//         :load enfa.scala)
+
+
+// states for Thompson construction
+case class TState(i: Int) extends State
+
+object TState {
+  var counter = 0
+  
+  def apply() : TState = {
+    counter += 1;
+    new TState(counter - 1)
+  }
+}
+
+
+// some types abbreviations
+type NFAt = NFA[TState, Char]
+type NFAtrans = (TState, Char) :=> Set[TState]
+type eNFAtrans = (TState, Option[Char]) :=> Set[TState]
+
+
+// for composing an eNFA transition with a NFA transition
+implicit class RichPF(val f: eNFAtrans) extends AnyVal {
+  def +++(g: NFAtrans) : eNFAtrans = 
+  { case (q, None) =>  applyOrElse(f, (q, None)) 
+    case (q, Some(c)) => applyOrElse(f, (q, Some(c))) | applyOrElse(g, (q, c))  }
+}
+
+
+// NFA that does not accept any string
+def NFA_ZERO(): NFAt = {
   val Q = TState()
   NFA(Set(Q), { case _ => Set() }, Set())
 }
 
-// eNFA that accepts the empty string
-def eNFA_ONE() : NFA[TState, Char] = {
+// NFA that accepts the empty string
+def NFA_ONE() : NFAt = {
   val Q = TState()
   NFA(Set(Q), { case _ => Set() }, Set(Q))
 }
 
-// eNFA that accepts the string "c"
-def eNFA_CHAR(c: Char) : NFA[TState, Char] = {
+// NFA that accepts the string "c"
+def NFA_CHAR(c: Char) : NFAt = {
   val Q1 = TState()
   val Q2 = TState()
   NFA(Set(Q1), { case (Q1, d) if (c == d) => Set(Q2) }, Set(Q2))
 }
 
-// alternative of two eNFAs
-def eNFA_ALT(enfa1: NFA[TState, Char], enfa2: NFA[TState, Char]) : NFA[TState, Char] = {
+// sequence of two NFAs
+def NFA_SEQ(enfa1: NFAt, enfa2: NFAt) : NFAt = {
+  val new_delta : eNFAtrans = 
+    { case (q, None) if enfa1.fins(q) => enfa2.starts }
+  
+  eNFA(enfa1.starts, new_delta +++ enfa1.delta +++ enfa2.delta, 
+       enfa2.fins)
+}
+
+// alternative of two NFAs
+def NFA_ALT(enfa1: NFAt, enfa2: NFAt) : NFAt = {
   val Q = TState()
   val new_delta : eNFAtrans = 
     { case (Q, None) => enfa1.starts | enfa2.starts }
-
   val new_fins = (q: TState) => enfa1.fins(q) || enfa2.fins(q)
 
-  eNFA(Set(Q), 
-       new_delta andAlso enfa1.delta andAlso enfa2.delta, 
-       new_fins)
+  eNFA(Set(Q), new_delta +++ enfa1.delta +++ enfa2.delta, new_fins)
 }
 
-// sequence of two eNFAs
-def eNFA_SEQ(enfa1: NFA[TState, Char], enfa2: NFA[TState, Char]) : NFA[TState, Char] = {
-  val new_delta : eNFAtrans = 
-    { case (q, None) if enfa1.fins(q) => enfa2.starts }
-  
-  eNFA(enfa1.starts, 
-       new_delta andAlso enfa1.delta andAlso enfa2.delta, 
-       enfa2.fins)
-}
-
-// star of an eNFA
-def eNFA_STAR(enfa: NFA[TState, Char]) : NFA[TState, Char] = {
+// star of a NFA
+def NFA_STAR(enfa: NFAt) : NFAt = {
   val Q = TState()
   val new_delta : eNFAtrans = 
     { case (Q, None) => enfa.starts
       case (q, None) if enfa.fins(q) => Set(Q) }
 
-  eNFA(Set(Q), new_delta andAlso enfa.delta, Set(Q))
+  eNFA(Set(Q), new_delta +++ enfa.delta, Set(Q))
+}
+
+
+
+// regular expressions
+abstract class Rexp
+case object ZERO extends Rexp                    // matches nothing
+case object ONE extends Rexp                     // matches the empty string
+case class CHAR(c: Char) extends Rexp            // matches a character c
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp  // alternative
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp  // sequence
+case class STAR(r: Rexp) extends Rexp            // star
+
+
+
+
+// thompson construction 
+def thompson (r: Rexp) : NFAt = r match {
+  case ZERO => NFA_ZERO()
+  case ONE => NFA_ONE()
+  case CHAR(c) => NFA_CHAR(c)  
+  case ALT(r1, r2) => NFA_ALT(thompson(r1), thompson(r2))
+  case SEQ(r1, r2) => NFA_SEQ(thompson(r1), thompson(r2))
+  case STAR(r1) => NFA_STAR(thompson(r1))
 }
+
+
+def tmatches(r: Rexp, s: String) : Boolean =
+  thompson(r).accepts(s.toList)
+
+def tmatches2(r: Rexp, s: String) : Boolean =
+  thompson(r).accepts2(s.toList)
+
+
+//optional regular expression (one or zero times)
+def OPT(r: Rexp) = ALT(r, ONE)
+
+//n-times regular expression (explicitly expanded)
+def NTIMES(r: Rexp, n: Int) : Rexp = n match {
+  case 0 => ONE
+  case 1 => r
+  case n => SEQ(r, NTIMES(r, n - 1))
+}
+
+
+// Test Cases
+
+// the evil regular expression  a?{n} a{n}
+def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
+
+// the evil regular expression (a*)*b
+val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+
+//for measuring time
+def time_needed[T](i: Int, code: => T) = {
+  val start = System.nanoTime()
+  for (j <- 1 to i) code
+  val end = System.nanoTime()
+  (end - start)/(i * 1.0e9)
+
+
+// the size of the NFA can be large, 
+// thus slowing down the breadth-first search
+
+for (i <- 1 to 10) {
+  println(i + ": " + "%.5f".format(time_needed(2, tmatches(EVIL1(i), "a" * i))))
+}
+
+for (i <- 1 to 10) {
+  println(i + " " + "%.5f".format(time_needed(2, tmatches(EVIL2, "a" * i))))
+}
+
+
+// the backtracking needed in depth-first search 
+// can be painfully slow
+
+for (i <- 1 to 8) {
+  println(i + " " + "%.5f".format(time_needed(2, tmatches2(EVIL2, "a" * i))))
+}