--- 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())
}
Binary file hws/hw02.pdf has changed
--- 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}
Binary file pics/DFA.png has changed
Binary file slides/slides03.pdf has changed
--- 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]
