--- a/progs/dfa.scala Thu Jul 25 14:39:37 2019 +0100
+++ b/progs/dfa.scala Sun Jul 28 01:00:41 2019 +0100
@@ -1,13 +1,13 @@
// DFAs in Scala using partial functions
import scala.util.Try
-// type abbreviation for partial functions
+// a type abbreviation for partial functions
type :=>[A, B] = PartialFunction[A, B]
-case class DFA[A, C](start: A, // starting state
- delta: (A, C) :=> A, // transition (partial fun)
- fins: A => Boolean) { // final states
+case class DFA[A, C](start: A, // the starting state
+ delta: (A, C) :=> A, // transitions (partial fun)
+ fins: A => Boolean) { // the final states
def deltas(q: A, s: List[C]) : A = s match {
case Nil => q
@@ -52,7 +52,7 @@
case object S2 extends S
case object Sink extends S
-// transition function with a sink state
+// a transition function with a sink state
val sigma : (S, Char) :=> S =
{ case (S0, 'a') => S1
case (S1, 'a') => S2
--- a/progs/enfa.scala Thu Jul 25 14:39:37 2019 +0100
+++ b/progs/enfa.scala Sun Jul 28 01:00:41 2019 +0100
@@ -2,7 +2,7 @@
// (needs :load dfa.scala
// :load nfa.scala in REPL)
-// fixpoint construction
+// a fixpoint construction
import scala.annotation.tailrec
@tailrec
def fixpT[A](f: A => A, x: A): A = {
@@ -11,9 +11,9 @@
}
// translates eNFAs directly into NFAs
-def eNFA[A, C](starts: Set[A], // starting states
- delta: (A, Option[C]) :=> Set[A], // epsilon-transitions
- fins: A => Boolean) : NFA[A, C] = { // final states
+def eNFA[A, C](starts: Set[A], // the starting states
+ delta: (A, Option[C]) :=> Set[A], // the epsilon-transitions
+ fins: A => Boolean) : NFA[A, C] = { // the final states
// epsilon transitions
def enext(q: A) : Set[A] =
--- a/progs/nfa.scala Thu Jul 25 14:39:37 2019 +0100
+++ b/progs/nfa.scala Sun Jul 28 01:00:41 2019 +0100
@@ -4,18 +4,18 @@
// needs :load dfa.scala for states
-// type abbreviation for partial functions
+// a type abbreviation for partial functions
type :=>[A, B] = PartialFunction[A, B]
-// return an empty set, when parial function is not defined
+// return an empty set, when a parial function is not defined
def applyOrElse[A, B](f: A :=> Set[B], x: A) : Set[B] =
Try(f(x)) getOrElse Set[B]()
// NFAs
-case class NFA[A, C](starts: Set[A], // starting states
- delta: (A, C) :=> Set[A], // transition function
- fins: A => Boolean) { // final states
+case class NFA[A, C](starts: Set[A], // the starting states
+ delta: (A, C) :=> Set[A], // the transition function
+ fins: A => Boolean) { // the final states
// given a state and a character, what is the set of
// next states? if there is none => empty set
--- a/progs/re1.scala Thu Jul 25 14:39:37 2019 +0100
+++ b/progs/re1.scala Sun Jul 28 01:00:41 2019 +0100
@@ -1,8 +1,8 @@
-// Simple matcher for basic regular expressions
+// A simple matcher for basic regular expressions
abstract class Rexp
case object ZERO extends Rexp // matches nothing
-case object ONE extends Rexp // matches the empty string
+case object ONE extends Rexp // matches an 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
@@ -19,9 +19,7 @@
case STAR(_) => true
}
-
-
-// derivative of a regular expression w.r.t. a character
+// the derivative of a regular expression w.r.t. a character
def der (c: Char, r: Rexp) : Rexp = r match {
case ZERO => ZERO
case ONE => ZERO
@@ -33,18 +31,18 @@
case STAR(r1) => SEQ(der(c, r1), STAR(r1))
}
-// derivative w.r.t. a string (iterates der)
+// the derivative w.r.t. a string (iterates der)
def ders (s: List[Char], r: Rexp) : Rexp = s match {
case Nil => r
case c::s => ders(s, der(c, r))
}
-// main matcher function
+// the main matcher function
def matches(r: Rexp, s: String) : Boolean =
nullable(ders(s.toList, r))
-//examples from the homework
+// examples from the homework
val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b')))
der('a', r)
@@ -57,10 +55,10 @@
der('z', der('y', der('x', r2)))
-//optional regular expression (one or zero times)
+// the optional regular expression (one or zero times)
def OPT(r: Rexp) = ALT(r, ONE)
-//n-times regular expression (explicitly expanded)
+// the n-times regular expression (explicitly expanded)
def NTIMES(r: Rexp, n: Int) : Rexp = n match {
case 0 => ONE
case 1 => r
@@ -76,40 +74,31 @@
// the evil regular expression (a*)*b
val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
-//for measuring time
+// 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)
+ "%.5f".format((end - start) / (i * 1.0e9))
}
-//test: (a?{n}) (a{n})
+// test: (a?{n}) (a{n})
println("Test (a?{n}) (a{n})")
-for (i <- 1 to 20) {
- println(i + ": " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i))))
-}
-for (i <- 1 to 20) {
- println(i + ": " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i))))
+for (i <- 0 to 20 by 2) {
+ println(s"$i: ${time_needed(2, matches(EVIL1(i), "a" * i))}")
}
-//test: (a*)* b
+// test: (a*)* b
println("Test (a*)* b")
-for (i <- 1 to 20) {
- println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i))))
-}
-
-for (i <- 1 to 20) {
- println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i))))
+for (i <- 0 to 20 by 2) {
+ println(s"$i: ${time_needed(2, matches(EVIL2, "a" * i))}")
}
-
-
-// size of a regular expressions - for testing purposes
+// the size of a regular expressions - for testing purposes
def size(r: Rexp) : Int = r match {
case ZERO => 1
case ONE => 1
@@ -126,7 +115,7 @@
size(EVIL1(3)) // 17
size(EVIL1(5)) // 29
size(EVIL1(7)) // 41
-
+size(EVIL1(20)) // 119
// given a regular expression and building successive
// derivatives might result into bigger and bigger
@@ -147,6 +136,6 @@
size(ders(("ab" * 200).toList, BIG)) // 366808
-for (i <- 1 to 21) {
- println(i + " " + "%.5f".format(time_needed(2, matches(BIG, "ab" * i))))
+for (i <- 0 to 200 by 10) {
+ println(s"$i: ${time_needed(2, matches(BIG, "ab" * i))}")
}
--- a/progs/re2.scala Thu Jul 25 14:39:37 2019 +0100
+++ b/progs/re2.scala Sun Jul 28 01:00:41 2019 +0100
@@ -1,4 +1,4 @@
-// Version with an explicit n-times regular expression;
+// A Version with an explicit n-times regular expression;
// this keeps the size of the regular expression in the
// EVIL1 test-case quite small
@@ -44,14 +44,14 @@
def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r))
-//optional regular expression: one or zero times
-//this regular expression is still defined in terms of ALT
+// the optional regular expression: one or zero times
+// this regular expression is still defined in terms of ALT
def OPT(r: Rexp) = ALT(r, ONE)
// Test Cases
-//evil regular expressions
+// evil regular expressions
def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
@@ -59,32 +59,23 @@
val start = System.nanoTime()
for (j <- 1 to i) code
val end = System.nanoTime()
- (end - start)/(i * 1.0e9)
-}
-
-
-//test: (a?{n}) (a{n})
-for (i <- 1 to 1201 by 100) {
- println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i))))
-}
-
-for (i <- 1 to 1201 by 100) {
- println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i))))
-}
-
-
-//test: (a*)* b
-for (i <- 1 to 21) {
- println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i))))
-}
-
-for (i <- 1 to 21) {
- println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i))))
+ "%.5f".format((end - start) / (i * 1.0e9))
}
-// size of a regular expressions - for testing purposes
+// test: (a?{n}) (a{n})
+for (i <- 0 to 1000 by 100) {
+ println(s"$i: ${time_needed(2, matches(EVIL1(i), "a" * i))}")
+}
+
+// test: (a*)* b
+for (i <- 1 to 21) {
+ println(s"$i: ${time_needed(2, matches(EVIL2, "a" * i))}")
+}
+
+
+// the size of a regular expressions - for testing purposes
def size(r: Rexp) : Int = r match {
case ZERO => 1
case ONE => 1
@@ -103,6 +94,7 @@
size(EVIL1(3)) // 7
size(EVIL1(5)) // 7
size(EVIL1(7)) // 7
+size(EVIL1(20)) // 7
size(ders("".toList, EVIL1(5))) // 7
size(ders("a".toList, EVIL1(5))) // 16
--- a/progs/re3.scala Thu Jul 25 14:39:37 2019 +0100
+++ b/progs/re3.scala Sun Jul 28 01:00:41 2019 +0100
@@ -14,7 +14,7 @@
-// nullable function: tests whether the regular
+// the nullable function: tests whether the regular
// expression can recognise the empty string
def nullable (r: Rexp) : Boolean = r match {
case ZERO => false
@@ -26,7 +26,7 @@
case NTIMES(r, i) => if (i == 0) true else nullable(r)
}
-// derivative of a regular expression w.r.t. a character
+// the derivative of a regular expression w.r.t. a character
def der (c: Char, r: Rexp) : Rexp = r match {
case ZERO => ZERO
case ONE => ZERO
@@ -57,35 +57,35 @@
}
-// derivative w.r.t. a string (iterates der)
+// the derivative w.r.t. a string (iterates der)
def ders(s: List[Char], r: Rexp) : Rexp = s match {
case Nil => r
case c::s => ders(s, simp(der(c, r)))
}
-// derivative w.r.t. a string (iterates der)
+// the derivative w.r.t. a string (iterates der)
def dersp(s: List[Char], r: Rexp) : Rexp = s match {
case Nil => r
case c::s => dersp(s, der(c, r))
}
-// main matcher function
+// the main matcher function
def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r))
-//tests
+// tests
val q = SEQ(SEQ(CHAR('x'), CHAR('y')), CHAR('z'))
dersp("x".toList, q)
dersp("xy".toList, q)
dersp("xyz".toList, q)
-//one or zero
+// one or zero
def OPT(r: Rexp) = ALT(r, ONE)
// Test Cases
-//evil regular expressions: (a?){n} a{n} and (a*)* b
+// evil regular expressions: (a?){n} a{n} and (a*)* b
def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
--- a/progs/re3a.scala Thu Jul 25 14:39:37 2019 +0100
+++ b/progs/re3a.scala Sun Jul 28 01:00:41 2019 +0100
@@ -9,7 +9,7 @@
case class NTIMES(r: Rexp, n: Int) extends Rexp
case class UPNTIMES(r: Rexp, n: Int) extends Rexp
-// nullable function: tests whether the regular
+// the nullable function: tests whether the regular
// expression can recognise the empty string
def nullable (r: Rexp) : Boolean = r match {
case ZERO => false
@@ -22,7 +22,7 @@
case UPNTIMES(r: Rexp, n: Int) => true
}
-// derivative of a regular expression w.r.t. a character
+// the derivative of a regular expression w.r.t. a character
def der (c: Char, r: Rexp) : Rexp = r match {
case ZERO => ZERO
case ONE => ZERO
@@ -58,20 +58,20 @@
}
-// derivative w.r.t. a string (iterates der)
+// the derivative w.r.t. a string (iterates der)
def ders (s: List[Char], r: Rexp) : Rexp = s match {
case Nil => r
case c::s => ders(s, simp(der(c, r)))
}
-// main matcher function
-def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r))
+// the main matcher function
+def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r))
-//one or zero
+// one or zero
def OPT(r: Rexp) = ALT(r, ONE)
-//evil regular expressions
+// evil regular expressions
def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
val EVIL3 = SEQ(STAR(ALT(CHAR('a'), SEQ(CHAR('a'),CHAR('a')))), CHAR('b'))
@@ -80,26 +80,18 @@
val start = System.nanoTime()
for (j <- 1 to i) code
val end = System.nanoTime()
- (end - start)/(i * 1.0e9)
+ "%.5f".format((end - start) / (i * 1.0e9))
}
-//test: (a?{n}) (a{n})
-for (i <- 1 to 8001 by 1000) {
- println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i))))
+// test: (a?{n}) (a{n})
+for (i <- 0 to 8000 by 1000) {
+ println(s"$i: ${time_needed(2, matches(EVIL1(i), "a" * i))}")
}
-for (i <- 1 to 8001 by 1000) {
- println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i))))
-}
-
-//test: (a*)* b
-for (i <- 1 to 6000001 by 500000) {
- println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i))))
-}
-
-for (i <- 1 to 6000001 by 500000) {
- println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i))))
+// test: (a*)* b
+for (i <- 0 to 6000000 by 500000) {
+ println(s"$i: ${time_needed(2, matches(EVIL2, "a" * i))}")
}
@@ -113,8 +105,8 @@
//test: (a|aa)* b
/*
-for (i <- 1 to 7001 by 500) {
- println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL3, "a" * i ++ "c"))))
+for (i <- 0 to 100 by 10) {
+ println(s"$i: ${time_needed(2, matches(EVIL3, "a" * i ++ "c"))}")
}
*/
--- a/progs/re4.scala Thu Jul 25 14:39:37 2019 +0100
+++ b/progs/re4.scala Sun Jul 28 01:00:41 2019 +0100
@@ -1,4 +1,4 @@
-// Version which attempts to move whole strings, not
+// A version which attempts to move whole strings, not
// just characters, under derivatives whenever possible
abstract class Rexp
@@ -10,7 +10,7 @@
case class STAR(r: Rexp) extends Rexp
case class NTIMES(r: Rexp, n: Int) extends Rexp
-// nullable function: tests whether the regular
+// the nullable function: tests whether the regular
// expression can recognise the empty string
def nullable (r: Rexp) : Boolean = r match {
case ZERO => false
@@ -22,7 +22,7 @@
case NTIMES(r, i) => if (i == 0) true else nullable(r)
}
-// derivative of a regular expression w.r.t. a character
+// the derivative of a regular expression w.r.t. a character
def der (c: Char, r: Rexp) : Rexp = r match {
case ZERO => ZERO
case ONE => ZERO
@@ -52,7 +52,7 @@
case r => r
}
-//example
+// an example
val r = SEQ(SEQ(CHAR('x'), CHAR('y')), CHAR('z'))
der('x', r)
der('y', der('x', r))
@@ -60,7 +60,7 @@
simp(der('z', der('y', der('x', r))))
// *new*
-// derivative w.r.t. a string (iterates der)
+// the derivative w.r.t. a string (iterates der)
def ders2(s: List[Char], r: Rexp) : Rexp = (s, r) match {
case (Nil, r) => r
case (s, ZERO) => ZERO
@@ -71,11 +71,11 @@
case (c::s, r) => ders2(s, simp(der(c, r)))
}
-// main matcher function
-def matcher(r: Rexp, s: String) : Boolean = nullable(ders2(s.toList, r))
+// the main matcher function
+def matches(r: Rexp, s: String) : Boolean = nullable(ders2(s.toList, r))
-//one or zero
+// one or zero
def OPT(r: Rexp) = ALT(r, ONE)
@@ -84,35 +84,29 @@
def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
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)
-}
-
-//test: (a?{n}) (a{n})
-for (i <- 1 to 7000001 by 500000) {
- println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i))))
+ "%.5f".format((end - start) / (i * 1.0e9))
}
-for (i <- 1 to 7000001 by 500000) {
- println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i))))
+
+// test: (a?{n}) (a{n})
+for (i <- 0 to 7000000 by 500000) {
+ println(s"$i: ${time_needed(2, matches(EVIL1(i), "a" * i))}")
}
-//test: (a*)* b
+
+// test: (a*)* b
for (i <- 1 to 7000001 by 500000) {
- println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i))))
-}
-
-for (i <- 1 to 7000001 by 500000) {
- println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i))))
+ println(s"$i: ${time_needed(2, matches(EVIL2, "a" * i))}")
}
-// size of a regular expressions - for testing purposes
+// the size of a regular expressions - for testing purposes
def size(r: Rexp) : Int = r match {
case ZERO => 1
case ONE => 1
@@ -140,7 +134,7 @@
// test: ("a" | "aa")*
val EVIL3 = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a'))))
-//test: ("" | "a" | "aa")*
+// test: ("" | "a" | "aa")*
val EVIL3 = STAR(ALT(ONE, ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))))
val t1 = ders2("a".toList, EVIL3)