# HG changeset patch # User Christian Urban # Date 1665703907 -3600 # Node ID 00c1c3408c935ef2827ed7e491a6d72402d58b7b # Parent fc812b8f120fb2150012f568684416440816fe5e updated diff -r fc812b8f120f -r 00c1c3408c93 cws/build.sc --- a/cws/build.sc Mon Oct 10 15:15:15 2022 +0100 +++ b/cws/build.sc Fri Oct 14 00:31:47 2022 +0100 @@ -1,12 +1,12 @@ #!/usr/bin/env amm -val files = List("cw01.tex", +val files = Seq("cw01.tex", "cw02.tex", "cw03.tex", "cw04.tex", "cw05.tex") - +val pdf_files = files.map(s => s.stripSuffix("tex") ++ "pdf") @main @@ -21,6 +21,6 @@ @main def hg() = { - println(s"$files") - println(os.proc("hg", "commit", "-m texupdate", files.mkString(" ")).call()) + println(os.proc("hg", "commit", "-m texupdate", files ++ pdf_files).call()) + println(os.proc("hg", "push").call()) } diff -r fc812b8f120f -r 00c1c3408c93 hws/hw02.pdf Binary file hws/hw02.pdf has changed diff -r fc812b8f120f -r 00c1c3408c93 hws/hw02.tex --- a/hws/hw02.tex Mon Oct 10 15:15:15 2022 +0100 +++ b/hws/hw02.tex Fri Oct 14 00:31:47 2022 +0100 @@ -1,5 +1,7 @@ \documentclass{article} \usepackage{../style} +\usepackage{../graphicss} + \newcommand{\solution}[1]{% \begin{quote}\sf% @@ -45,7 +47,70 @@ 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], []\}$} + $A = \{[a]\}$, $B = \{[]\}$ and $C = \{[a], []\}$\medskip + + For equations like 3 it is always a god idea to prove the + two inclusions + + \[ + A^* \subseteq A^* @ A^* \qquad + A^* @ A^* \subseteq A^* + \] + + This means for every string $s$ we have to show + + \[ + s \in A^* \;\textit{implies}\; s \in A^* @ A^* \qquad + s \in A^* @ A^* \;\textit{implies}\; s \in A^* + \] + + The first one is easy because $[] \in A^*$ and therefore + $s @ [] \in A^* @ A^*$. + + The second one says that $s$ must be of the form $s = s_1 @ s_2$ with + $s_1 \in A^*$ and $s_2 \in A^*$. We have to show that + $s_1 @ s_2 \in A^*$. + + If $s_1 \in A^*$ then there exists an $n$ such that $s_1 \in A^n$, and + 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 + + \[ + A^n \,@\, A^m = A^{n+m} + \] + + We prove that by induction on $n$. + + Case $n = 0$: $A^0 \,@\, A^m = A^{0+m}$ holds because $A^0 = \{[]\}$ + and $\{[]\} \,@\, A^m = A ^ m$ and $0 + m = m$.\medskip + + Case $n + 1$: The induction hypothesis is + + \[ A^n \,@\, A^m = A^{n+m} + \] + + We need to prove + + \[ + A^{n+1} \,@\, A^m = A^{(n+1)+m} + \] + + The left-hand side is $(A \,@\, A^n) \,@\, A^m$ by the definition of + the power operation. We can rearrange that + to $A \,@\, (A^n \,@\, A^m)$. \footnote{Because for all languages $A$, $B$, $C$ we have $(A @ B) @ C = A @ (B @ C)$.} + + By the induction hypothesis we know that $A^n \,@\, A^m = A^{n+m}$. + + So we have $A \,@\, (A^{n+m})$. But this is $A^{(n+m)+1}$ again if we + apply the definition of the power operator. If we + rearrange that we get $A^{(n+1)+m}$ and are done with + what we need to prove for the power law.\bigskip + + Picking up where we left, we know that $s_1 \in A^n$ and $s_2 \in A^m$. This now implies that $s_1 @ s_2\in A^n @ A^m$. By the power law this means + $s_1 @ s_2\in A^{n+m}$. But this also means $s_1 @ s_2\in A^*$. + } \item Given the regular expressions $r_1 = \ONE$ and $r_2 = \ZERO$ and $r_3 = a$. How many strings can the regular @@ -100,12 +165,13 @@ recognising all strings that do not contain any substring $bb$ and end in $a$. - + \solution{$((ba)^* \cdot (a)^*)^*\,\cdot\,a$} \item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) + (b^*\cdot b^+)$ define the same language? - \solution{No, the first one can match for example abababababbbbb} + \solution{No, the first one can match for example abababababbbbb + while the second can only match for example aaaaaabbbbb or bbbbbbb} \item Define the function $zeroable$ by recursion over regular expressions. This function should satisfy the property @@ -128,7 +194,33 @@ zeroable(\sim r) \dn \neg(zeroable(r)) \] - Find a counter example? + Find a counter example? + + + \solution{ + Here the idea is that nullable for NOT can be defined as + + \[nullable(\sim r) \dn \neg(nullable(r))\] + + This will satisfy the property + $nullable(r) \;\;\text{if and only if}\;\;[] \in L(r)$. (Remember how + $L(\sim r)$ is defined).\bigskip + + But you cannot define + + \[zeroable(\sim r) \dn \neg(zeroable(r))\] + + because if $r$ for example is $\ONE$ then $\sim \ONE$ can match + some strings (all non-empty strings). So $zeroable$ should be false. But if we follow + the above definition we would obtain $\neg(zeroable(\ONE))$. According + to the definition of $zeroable$ for $\ONE$ this would be false, + but if we now negate false, we get actually true. So the above + definition would not satisfy the property + + \[ + zeroable(r) \;\;\text{if and only if}\;\;L(r) = \{\} + \] + } \item Give a regular expressions that can recognise all strings from the language $\{a^n\;|\;\exists k.\; n = 3 k @@ -137,7 +229,42 @@ \solution{$a(aaa)^*$} \item Give a regular expression that can recognise an odd -number of $a$s or an even number of $b$s. + number of $a$s or an even number of $b$s. + + \solution{ + If the a's and b's are meant to be separate, then this is easy + + \[a(aa)^* + (bb)^*\] + + If the letters are mixed, then this is difficult + + \[(aa|bb|(ab|ba)\cdot (aa|bb)^* \cdot (ba|ab))^* \cdot (b|(ab|ba)(bb|aa)^* \cdot a) + \] + + (copied from somewhere ;o) + + The idea behind it is essentially the DFA + +\begin{center} +\begin{tikzpicture}[scale=1,>=stealth',very thick, + every state/.style={minimum size=0pt, + draw=blue!50,very thick,fill=blue!20}] + \node[state,initial] (q0) at (0,2) {$q_0$}; + \node[state,accepting] (q1) at (2,2) {$q_1$}; + \node[state] (q2) at (0,0) {$q_2$}; + \node[state] (q3) at (2,0) {$q_3$}; + + \path[->] (q0) edge[bend left] node[above] {$a$} (q1) + (q1) edge[bend left] node[above] {$a$} (q0) + (q2) edge[bend left] node[above] {$a$} (q3) + (q3) edge[bend left] node[above] {$a$} (q2) + (q0) edge[bend left] node[right] {$b$} (q2) + (q2) edge[bend left] node[left] {$b$} (q0) + (q1) edge[bend left] node[right] {$b$} (q3) + (q3) edge[bend left] node[left] {$b$} (q1); +\end{tikzpicture} +\end{center} +} \item \POSTSCRIPT \end{enumerate} diff -r fc812b8f120f -r 00c1c3408c93 pics/DFA.png Binary file pics/DFA.png has changed diff -r fc812b8f120f -r 00c1c3408c93 slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r fc812b8f120f -r 00c1c3408c93 slides/slides03.tex --- a/slides/slides03.tex Mon Oct 10 15:15:15 2022 +0100 +++ b/slides/slides03.tex Fri Oct 14 00:31:47 2022 +0100 @@ -27,19 +27,20 @@ \frametitle{% \begin{tabular}{@ {}c@ {}} \\[-3mm] - \LARGE Compilers and \\[-2mm] - \LARGE Formal Languages\\[3mm] + \LARGE Compilers and \\[-1mm] + \LARGE Formal Languages\\[-5mm] \end{tabular}} \normalsize \begin{center} \begin{tabular}{ll} - Email: & christian.urban at kcl.ac.uk\\ - %Office Hours: & Thursdays 12 -- 14\\ - %Location: & N7.07 (North Wing, Bush House)\\ - Slides \& Progs: & KEATS (also homework is there)\\ + Email: & christian.urban at kcl.ac.uk\\ + Office Hour: & Fridays 11 -- 12\\ + Location: & N7.07 (North Wing, Bush House)\\ + Slides \& Progs: & KEATS\\ + Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\ \end{tabular} -\end{center} + \end{center} \begin{center} \begin{tikzpicture} @@ -1705,6 +1706,38 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +{ +\setbeamercolor{background canvas}{bg=cream} +\begin{frame}[c] + +\begin{center} +\begin{tikzpicture}[scale=1.5,>=stealth',very thick, + every state/.style={minimum size=0pt, + draw=blue!50,very thick,fill=blue!20}] + \node[state,initial] (q0) at (0,2) {$q_0$}; + \node[state,accepting] (q1) at (2,2) {$q_1$}; + \node[state] (q2) at (0,0) {$q_2$}; + \node[state] (q3) at (2,0) {$q_3$}; + + \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) + (q1) edge[bend left] node[above] {\alert{$a$}} (q0) + (q2) edge[bend left] node[above] {\alert{$a$}} (q3) + (q3) edge[bend left] node[above] {\alert{$a$}} (q2) + (q0) edge[bend left] node[right] {\alert{$b$}} (q2) + (q2) edge[bend left] node[left] {\alert{$b$}} (q0) + (q1) edge[bend left] node[right] {\alert{$b$}} (q3) + (q3) edge[bend left] node[left] {\alert{$b$}} (q1); +\end{tikzpicture} +\end{center} + +\hfill{}Which language? + +\end{frame} +} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + \begin{frame}<1-15>[c]