progs/automata/thompson.sc
changeset 779 5385c8342f02
parent 753 d94fdbef1a4f
child 784 7dac4492b0e6
--- a/progs/automata/thompson.sc	Sun Oct 11 09:10:08 2020 +0100
+++ b/progs/automata/thompson.sc	Tue Oct 13 14:29:10 2020 +0100
@@ -55,33 +55,33 @@
 
 
 // sequence of two NFAs
-def NFA_SEQ(enfa1: NFAt, enfa2: NFAt) : NFAt = {
+def NFA_SEQ(nfa1: NFAt, nfa2: NFAt) : NFAt = {
   val new_delta : eNFAtrans = 
-    { case (q, None) if enfa1.fins(q) => enfa2.starts }
+    { case (q, None) if nfa1.fins(q) => nfa2.starts }
   
-  eNFA(enfa1.starts, 
-       new_delta +++ enfa1.delta +++ enfa2.delta, 
-       enfa2.fins)
+  eNFA(nfa1.starts, 
+       new_delta +++ nfa1.delta +++ nfa2.delta, 
+       nfa2.fins)
 }
 
 // alternative of two NFAs
-def NFA_ALT(enfa1: NFAt, enfa2: NFAt) : NFAt = {
+def NFA_ALT(nfa1: NFAt, nfa2: NFAt) : NFAt = {
   val new_delta : NFAtrans = { 
-    case (q, c) =>  applyOrElse(enfa1.delta, (q, c)) | 
-                    applyOrElse(enfa2.delta, (q, c)) }
-  val new_fins = (q: TState) => enfa1.fins(q) || enfa2.fins(q)
+    case (q, c) =>  applyOrElse(nfa1.delta, (q, c)) | 
+                    applyOrElse(nfa2.delta, (q, c)) }
+  val new_fins = (q: TState) => nfa1.fins(q) || nfa2.fins(q)
 
-  NFA(enfa1.starts | enfa2.starts, new_delta, new_fins)
+  NFA(nfa1.starts | nfa2.starts, new_delta, new_fins)
 }
 
 // star of a NFA
-def NFA_STAR(enfa: NFAt) : NFAt = {
+def NFA_STAR(nfa: NFAt) : NFAt = {
   val Q = TState()
   val new_delta : eNFAtrans = 
-    { case (Q, None) => enfa.starts
-      case (q, None) if enfa.fins(q) => Set(Q) }
+    { case (Q, None) => nfa.starts
+      case (q, None) if nfa.fins(q) => Set(Q) }
 
-  eNFA(Set(Q), new_delta +++ enfa.delta, Set(Q))
+  eNFA(Set(Q), new_delta +++ nfa.delta, Set(Q))
 }
 
 
@@ -147,6 +147,7 @@
 
 // the size of the NFA can be large, 
 // thus slowing down the breadth-first search
+println("Breadth-first search EVIL1 / EVIL2")
 
 for (i <- 1 to 13) {
   println(i + ": " + "%.5f".format(time_needed(2, tmatches_nfa(EVIL1(i), "a" * i))))
@@ -159,8 +160,13 @@
 
 // the backtracking that is needed in depth-first 
 // search can be painfully slow
+println("Depth-first search EVIL1 / EVIL2")
 
-for (i <- 1 to 8) {
+for (i <- 1 to 9) {
+  println(i + " " + "%.5f".format(time_needed(2, tmatches_nfa2(EVIL1(i), "a" * i))))
+}
+
+for (i <- 1 to 7) {
   println(i + " " + "%.5f".format(time_needed(2, tmatches_nfa2(EVIL2, "a" * i))))
 }