--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/hws/build.sc Mon Sep 25 13:14:34 2023 +0100
@@ -0,0 +1,39 @@
+#!/usr/bin/env amm
+
+val files = Seq("hw01.tex",
+ "hw02.tex",
+ "hw03.tex",
+ "hw04.tex",
+ "hw05.tex",
+ "hw06.tex",
+ "hw07.tex",
+ "hw08.tex",
+ "hw09.tex")
+
+val pdf_files = files.map(s => s.stripSuffix("tex") ++ "pdf")
+
+
+@main
+def make() = {
+ for (f <- files) {
+ println(s"Processing $f ...")
+ os.proc("lualatex", f).call(stdout = os.Inherit, stdin = os.Inherit)
+ }
+}
+
+@main
+def make_sols() = {
+ for (f <- files) {
+ val old_pdf = f.stripSuffix(".tex") ++ ".pdf"
+ val new_pdf = f.stripSuffix(".tex") ++ "-sol.pdf"
+ println(s"Processing $f -> $new_pdf ...")
+ os.proc("lualatex", f, "sol").call(stdout = os.Inherit, stdin = os.Inherit)
+ os.move.over(os.pwd / old_pdf, os.pwd / new_pdf)
+ }
+}
+
+@main
+def hg() = {
+ println(os.proc("hg", "commit", "-m texupdate", files ++ pdf_files).call())
+ println(os.proc("hg", "push").call())
+}
Binary file hws/hw01.pdf has changed
Binary file hws/hw02.pdf has changed
--- a/hws/hw02.tex Sat Sep 23 23:53:06 2023 +0100
+++ b/hws/hw02.tex Mon Sep 25 13:14:34 2023 +0100
@@ -39,9 +39,10 @@
explanation; otherwise give a counter-example.
\solution{1 + 3 are equal; 2 + 4 are not. Interesting is 4 where
- $A = \{[a]\}$, $B = \{[]\}$ and $C = \{[a], []\}$\medskip
+ $A = \{[a]\}$, $B = \{[]\}$ and $C = \{[a], []\}$ is an
+ counter-example.\medskip
- For equations like 3 it is always a god idea to prove the
+ For equations like 3 it is always a good idea to prove the
two inclusions
\[
@@ -67,7 +68,7 @@
if $s_2 \in A^*$ then there exists an $m$ such that $s_2 \in A^m$.\bigskip
- Aside: We are going to show that
+ Aside: We are going to show the following power law
\[
A^n \,@\, A^m = A^{n+m}
@@ -127,20 +128,66 @@
\solution{Both are equivalent, but why the second? Essentially you have to show that each string in one set is in the other. For 2 this means you can do an induction proof that $(ab)^na$ is the same string as $a(ba)^n$, where the former is in the first set and the latter in the second.}
-\item Given the regular expression $r = (a \cdot b + b)^*$.
- Compute what the derivative of $r$ is with respect to
- $a$, $b$ and $c$. Is $r$ nullable?
\item Give an argument for why the following holds:
if $r$ is nullable then $r^{\{n\}} \equiv r^{\{..n\}}$.
- \solution{This was from last week; I just explicitly added it here.}
+ \solution{ This requires an inductive proof. There are a number of
+ ways to prove this. It is clear that if $s \in L (r^{\{n\}})$ then
+ also $s \in L (r^{\{..n\}})$.
+
+ So one way to prove this is to show
+ that if $s \in L (r^{\{..n\}})$ then also $s \in L (r^{\{n\}})$
+ (under the assumption that $r$ is nullable, otherwise it would not
+ be true). The assumption $s \in L (r^{\{..n\}})$ means
+ that $s \in L(r^{\{i\}})$ with $i \leq n$ holds
+ and we have to show that $s \in L(r^{\{n\}})$ holds.
+
+ One can do this by induction for languages as follows:
+
+ \[
+ \textit{if}\; [] \in A \;\textit{and}\; s \in A^n
+ \;\textit{then}\; s \in A^{n+m}
+ \]
+
+ The proof is by induction on $m$. The base case $m=0$ is trivial.
+ For the $m + 1$ case we have the induction hypothesis:
+
+ \[
+ \textit{if}\; [] \in A \;\textit{and}\; s \in A^n
+ \;\textit{then}\; s \in A^{n+m}
+ \]
+
+ and we have to show
+
+ \[
+ s \in A^{n+m+1}
+ \]
+
+ under the assumption $[] \in A$ and $s \in A^n$. From the
+ assumptions and the IH we can infer that $s\in A^{n + m}$.
+ Then using the assumption $[] \in A$ we can infer that also
+
+ \[
+ s\in A \,@\, A^{n + m}
+ \]
+
+ which is equivalent to what we need to show $s \in A^{n+m+1}$.
+
+ Now we know $s \in L(r^{\{i\}})$ with $i \leq n$. Since $i + m = n$
+ for some $m$ we can conclude that $s \in L(r^{\{n\}})$. Done.
+
+ }
+
+\item Given the regular expression $r = (a \cdot b + b)^*$.
+ Compute what the derivative of $r$ is with respect to
+ $a$, $b$ and $c$. Is $r$ nullable?
\item Define what is meant by the derivative of a regular
expressions with respect to a character. (Hint: The
derivative is defined recursively.)
- \solution{the recursive function for $der$}
+ \solution{The recursive function for $der$.}
\item Assume the set $Der$ is defined as
@@ -235,7 +282,7 @@
(copied from somewhere ;o)
- The idea behind it is essentially the DFA
+ The idea behind this monstrous regex is essentially the DFA
\begin{center}
\begin{tikzpicture}[scale=1,>=stealth',very thick,
@@ -256,6 +303,10 @@
(q3) edge[bend left] node[left] {$b$} (q1);
\end{tikzpicture}
\end{center}
+
+ Maybe a good idea to reconsider this example in Lecture 3
+ where the Brzozowski algorithm for DFA $\rightarrow$ Regex
+ can be used.
}
\item \POSTSCRIPT
Binary file hws/hw03.pdf has changed
Binary file hws/hw04.pdf has changed
Binary file hws/hw05.pdf has changed
Binary file hws/hw06.pdf has changed
Binary file hws/hw07.pdf has changed
Binary file hws/hw08.pdf has changed
Binary file hws/hw09.pdf has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/hws/upload Mon Sep 25 13:14:34 2023 +0100
@@ -0,0 +1,20 @@
+#!/bin/bash
+set -euo pipefail
+
+fls=${1:-"hw01.pdf
+ hw02.pdf
+ hw03.pdf
+ hw04.pdf
+ hw05.pdf
+ hw06.pdf
+ hw07.pdf
+ hw08.pdf
+ hw09.pdf"}
+
+for f in $fls; do
+ echo -e "uploading $f"
+done
+
+
+scp $fls k1192855@bastion:public_html/cfl/hws/
+
--- a/progs/matcher/re1.sc Sat Sep 23 23:53:06 2023 +0100
+++ b/progs/matcher/re1.sc Mon Sep 25 13:14:34 2023 +0100
@@ -121,6 +121,9 @@
}
}
+
+
+
// the size of a regular expressions - for testing purposes
def size(r: Rexp) : Int = r match {
case ZERO => 1
@@ -147,34 +150,31 @@
// derivatives might result into bigger and bigger
// regular expressions...here is an example for this:
-// (a+b)* o a o b o (a+b)*
-val BIG_aux = STAR(ALT(CHAR('a'), CHAR('b')))
-val BIG = SEQ(BIG_aux, SEQ(CHAR('a'),SEQ(CHAR('b'), BIG_aux)))
+
+// (a + aa)*
+val BIG = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a'))))
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("aa".toList, BIG)) // 51
+size(ders("aaaa".toList, BIG)) // 112
+size(ders("aaaaaa".toList, BIG)) // 191
+size(ders("aaaaaaaa".toList, BIG)) // 288
+size(ders("aaaaaaaaaa".toList, BIG)) // 403
+size(ders("aaaaaaaaaaaa".toList, BIG)) // 536
-size(ders(("ab" * 200).toList, BIG)) // 366808
+size(ders(("a" * 30).toList, BIG)) // 31010539
-@arg(doc = "Test (a + b)* o (a o b) o (a + b)*")
@main
def test3() = {
- println("Test (a + b)* o (a o b) o (a + b)*")
+ println("Test (a + aa)*")
- for (i <- 0 to 200 by 10) {
- println(f"$i: ${time_needed(2, matcher(BIG, "ab" * i))}%.5f")
+ for (i <- 0 to 30 by 5) {
+ println(f"$i: ${time_needed(2, matcher(BIG, "a" * i))}%.5f")
}
}
-
-
@arg(doc = "All tests.")
@main
def all() = { test1(); test2() ; test3() }