--- 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))))
}