diff -r bd6d999ab7b6 -r 8178fcf377dc progs/thompson.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/thompson.scala	Tue Apr 25 12:33:16 2017 +0100
@@ -0,0 +1,51 @@
+// eNFA that does not accept any string
+def eNFA_ZERO(): NFA[TState, Char] = {
+  val Q = TState()
+  NFA(Set(Q), { case _ => Set() }, Set())
+}
+
+// eNFA that accepts the empty string
+def eNFA_ONE() : NFA[TState, Char] = {
+  val Q = TState()
+  NFA(Set(Q), { case _ => Set() }, Set(Q))
+}
+
+// eNFA that accepts the string "c"
+def eNFA_CHAR(c: Char) : NFA[TState, Char] = {
+  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] = {
+  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)
+}
+
+// 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] = {
+  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))
+}