# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1489752958 0
# Node ID 52aa298211f69c59f3f4211c66f7cec1b19c13d9
# Parent  48b842c997c7f0624207873f9530ff043776a5c6
updated

diff -r 48b842c997c7 -r 52aa298211f6 handouts/ho02.pdf
Binary file handouts/ho02.pdf has changed
diff -r 48b842c997c7 -r 52aa298211f6 handouts/ho02.tex
--- a/handouts/ho02.tex	Wed Mar 15 14:34:10 2017 +0000
+++ b/handouts/ho02.tex	Fri Mar 17 12:15:58 2017 +0000
@@ -265,6 +265,22 @@
 $\ZERO$s, therefore simplifying them away will make the
 algorithm quite a bit faster.
 
+Finally here are three equivalences between regulare expressions which are
+not so obvious:
+
+\begin{center}
+\begin{tabular}{rcl}
+$r^*$  & $\equiv$ & $1 + r\cdot r^*$\\
+$(r_1 + r_2)^*$  & $\equiv$ & $r_1^* \cdot (r_2\cdot r_1^*)^*$\\
+$(r_1 \cdot r_2)^*$ & $\equiv$ & $1 + r_1\cdot (r_2 \cdot r_1)^* \cdot r_2$\\
+\end{tabular}
+\end{center}
+
+\noindent
+You can try to establish them. As an aside, there has been a lot of research
+in questions like: Can one always decide when two regular expressions are
+equivalent or not? What does an algorithm look like to decide this?
+
 \subsection*{The Matching Algorithm}
 
 The algorithm we will define below consists of two parts. One
diff -r 48b842c997c7 -r 52aa298211f6 progs/dfa.scala
--- a/progs/dfa.scala	Wed Mar 15 14:34:10 2017 +0000
+++ b/progs/dfa.scala	Fri Mar 17 12:15:58 2017 +0000
@@ -1,3 +1,71 @@
+// convert normal string to hex bytes string
+def string2hex(str: String): String = {
+  str.toList.map(_.toInt.toHexString).mkString
+}
+    
+// convert hex bytes string to normal string
+
+
+val byteArray: Array[Byte] = List.range(1, 255).map(_.toByte).toArray
+val bos = new BufferedOutputStream(new FileOutputStream("test.txt"))
+bos.write(byteArray)
+bos.close() 
+
+
+def string2int(hex: String) = {
+  hex.sliding(2, 2).map(Integer.parseInt(_, 16)).toArray
+}
+
+def test(l: List[Int]) = {
+  l.map(_.toChar).mkString
+}
+
+
+import java.io._
+val writer = new PrintWriter(new File("test.txt" ))
+
+//writer.write(string2int("cafebabe"))
+writer.write(test(List.range(1, 255)))
+writer.close()
+
+import scalax.io._
+import scalax.io.Resource
+
+FileOutputStream fos = new FileOutputStream("test");
+fos.write(bytesArray);
+fos.close();
+
+
+string2int("cafebabe")
+
+202.toHexString
+
+"cafebabe".sliding(1, 1).toList.map(Integer.parseInt(_, 16)).map(_.toByte).map(_.toChar)
+
+hex2string("ca")
+string2hex("ca")
+hex2string("cafebabe")
+
+    
+val appkey = "9GLV//lv/kYFW2o3/bihxwnMcmo="
+        
+        // string to hex
+        val appkey_hex = string2hex(appkey)
+        // 39474c562f2f6c762f6b594657326f332f62696878776e4d636d6f3d
+        println(appkey_hex)
+        
+        // hex to string
+        val appkey_string_again = hex2string(appkey_hex)
+        // 9GLV//lv/kYFW2o3/bihxwnMcmo=
+        println(appkey_string_again)
+    }
+
+
+List("ca", "fe", "ba", "be").map(_.toByte)
+
+"ca".toByte
+
+
 // DFAs
 import scala.util._
 
diff -r 48b842c997c7 -r 52aa298211f6 progs/re1.scala
--- a/progs/re1.scala	Wed Mar 15 14:34:10 2017 +0000
+++ b/progs/re1.scala	Fri Mar 17 12:15:58 2017 +0000
@@ -115,3 +115,23 @@
 size(EVIL1(3))  // 17
 size(EVIL1(5))  // 29
 size(EVIL1(7))  // 41
+
+
+// given a regular expression and building successive
+// derivatives might result into bigger and bigger
+// regular expressions...here is an example for this:
+
+val BIG_aux = STAR(ALT(CHAR('a'), CHAR('b')))
+val BIG = SEQ(BIG_aux, SEQ(CHAR('a'),SEQ(CHAR('b'), BIG_aux)))
+
+size(ders("".toList, BIG))              // 13
+size(ders("ab".toList, BIG))            // 51
+size(ders("abab".toList, BIG))          // 112
+size(ders("ababab".toList, BIG))        // 191
+size(ders("abababab".toList, BIG))      // 288
+size(ders("ababababab".toList, BIG))    // 403
+size(ders("abababababab".toList, BIG))  // 536
+
+
+size(ders(("ab" * 200).toList, BIG))    // 366808
+