--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/display/thompson1.scala	Tue Sep 26 14:08:49 2017 +0100
@@ -0,0 +1,41 @@
+// Thompson Construction (Part 1)
+// (needs  :load dfa.scala
+//         :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)
+  }
+}
+
+
+// a type abbreviation
+type NFAt = NFA[TState, Char]
+
+
+// a NFA that does not accept any string
+def NFA_ZERO(): NFAt = {
+  val Q = TState()
+  NFA(Set(Q), { case _ => Set() }, Set())
+}
+
+// a NFA that accepts the empty string
+def NFA_ONE() : NFAt = {
+  val Q = TState()
+  NFA(Set(Q), { case _ => Set() }, Set(Q))
+}
+
+// a 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))
+}