# HG changeset patch # User Christian Urban # Date 1695644074 -3600 # Node ID 2f3c077359c4e412f9fc150df85d9da2d4d48263 # Parent ef54868a922695df46cb38ee85d8c78cc2ad0b46 updated diff -r ef54868a9226 -r 2f3c077359c4 hws/build.sc --- /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()) +} diff -r ef54868a9226 -r 2f3c077359c4 hws/hw01.pdf Binary file hws/hw01.pdf has changed diff -r ef54868a9226 -r 2f3c077359c4 hws/hw02.pdf Binary file hws/hw02.pdf has changed diff -r ef54868a9226 -r 2f3c077359c4 hws/hw02.tex --- 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 diff -r ef54868a9226 -r 2f3c077359c4 hws/hw03.pdf Binary file hws/hw03.pdf has changed diff -r ef54868a9226 -r 2f3c077359c4 hws/hw04.pdf Binary file hws/hw04.pdf has changed diff -r ef54868a9226 -r 2f3c077359c4 hws/hw05.pdf Binary file hws/hw05.pdf has changed diff -r ef54868a9226 -r 2f3c077359c4 hws/hw06.pdf Binary file hws/hw06.pdf has changed diff -r ef54868a9226 -r 2f3c077359c4 hws/hw07.pdf Binary file hws/hw07.pdf has changed diff -r ef54868a9226 -r 2f3c077359c4 hws/hw08.pdf Binary file hws/hw08.pdf has changed diff -r ef54868a9226 -r 2f3c077359c4 hws/hw09.pdf Binary file hws/hw09.pdf has changed diff -r ef54868a9226 -r 2f3c077359c4 hws/upload --- /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/ + diff -r ef54868a9226 -r 2f3c077359c4 progs/matcher/re1.sc --- 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() }