Binary file hws/hw01.pdf has changed

Binary file hws/hw02.pdf has changed

Binary file hws/hw03.pdf has changed

Binary file hws/hw04.pdf has changed

Binary file hws/hw05.pdf has changed

--- a/hws/hw05.tex	Tue Oct 31 12:52:36 2023 +0000
+++ b/hws/hw05.tex	Sat Nov 04 18:28:09 2023 +0000
@@ -40,6 +40,11 @@
        \sim r$
 \end{center}
 
+\solution{
+  There is the obvious solution $\sim{}\ZERO$, but also $a + \sim{}a$ would work.
+}  
+     
+
 %\item Assume the delimiters for comments are \texttt{$\slash$*}
 %and \texttt{*$\slash$}. Give a regular expression that can
 %recognise comments of the form
@@ -58,7 +63,7 @@
 $r^+$ & (one or more matches)\\
 $r^?$   & (zero or one match)\\
 $r^{\{n\}}$ & (exactly $n$ matches)\\
-$r^{\{m, n\}}$ & (at least $m$ and maximal $n$ matches, with the\\
+$r^{\{m.. n\}}$ & (at least $m$ and maximal $n$ matches, with the\\
 &  \phantom{(}assumption $m \le n$)\\
 \end{tabular}
 \end{center}
@@ -69,6 +74,20 @@
 $r ::= \ZERO \;|\; \ONE \;|\; c  \;|\; r_1 + r_2  \;|\; r_1 \cdot r_2 \;|\; r^*$
 \end{center}
 
+\solution{
+  $r^+ \dn r\cdot r^*$\\
+  $r^? \dn r + 1$\\
+  $r^{\{0\}} = \ONE$\\
+  $r^{\{n\}} \dn r\cdot r^{\{n-1\}}$\\
+  $r^{\{..n\}} \dn (r^?)^{\{n\}}$\\
+  $r^{\{n..m\}} \dn r^{\{..m-n\}}\cdot r^{\{n\}}$\\
+
+  BTW, $r^{\{n..m\}}$ cannot be defined in terms of $r^{\{n..\}} \;\&\; r^{\{..m\}}$ where $\&$ is
+  the intersection operator I introduced this year. For example assume $r=aaa + aaaaaaa$, then 
+  $r^{\{4..6\}}$ cannot match 21 a's, but $r^{\{4..\}} \;\&\; r^{\{..6\}}$.
+  }
+
+
 \item Give the regular expressions for lexing a language
       consisting of identifiers, left-parenthesis \texttt{(},
       right-parenthesis \texttt{)}, numbers that can be either
@@ -88,6 +107,10 @@
 Observe the maximal munch rule and the priorities of your regular
 expressions that make the process of lexing unambiguous.)
 
+\solution{
+  The first two strings can be lexed. But not the last ($/$ is not part of the language).
+}
+
 \item Suppose the following context-free grammar $G$
   
 \begin{plstx}[margin=1cm]
@@ -109,6 +132,15 @@
 \item[$\bullet$] $baa$
 \end{itemize}
 
+\solution{
+  The first and the last cannot be matched. Maybe it is a good exercise to
+  write down the derivations for the rest.
+
+  BTW, the language recognised by this grammar is strings consisting of
+  a's and b's where there are equal or more number of b's than a's (including the
+  empty string).
+}
+
 \item Suppose the following context-free grammar 
   
   \begin{plstx}[margin=1cm]
@@ -117,7 +149,11 @@
   \end{plstx}
 
 Describe which language is generated by this grammar.
-  
+
+\solution{Palindromes with the same number of a's and b's, including
+  the empty string}
+
+
 \item Remember we have specified identifiers with regular expressions as
   strings that start with a letter followed by letters, digits and
   underscores. This can also be specified by a grammar rule or rules.

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

Binary file hws/proof.pdf has changed

--- a/hws/proof.tex	Tue Oct 31 12:52:36 2023 +0000
+++ b/hws/proof.tex	Sat Nov 04 18:28:09 2023 +0000
@@ -86,11 +86,11 @@
 
 \begin{itemize}
 \item First Case: $P(\ZERO)$ is $L(der\,c\,\ZERO) = Der\,c\,(L(\ZERO))$ (a). We have $der\,c\,\ZERO = \ZERO$ 
-and $L(\ZERO) = \ZERO$. We also have $Der\,c\,\ZERO = \ZERO$. Hence we have $\ZERO = \ZERO$ in (a). 
+and $L(\ZERO) = \emptyset$. We also have $Der\,c\,L(\ZERO) = L(\ZERO$). Hence we have $\emptyset = \emptyset$ in (a). 
 
 \item Second  Case: $P(\ONE)$ is $L(der\,c\,\ONE) = Der\,c\,(L(\ONE))$ (b). We have $der\,c\,\ONE = \ZERO$,
-$L(\ZERO) = \ZERO$ and $L(\ONE) = \{\texttt{""}\}$. We also have $Der\,c\,\{\texttt{""}\} = \ZERO$. Hence we have 
-$\ZERO = \ZERO$ in (b). 
+$L(\ZERO) = \ZERO$ and $L(\ONE) = \{\texttt{""}\}$. We also have $Der\,c\,\{\texttt{""}\} = \emptyset$. Hence we have 
+$\emptyset = \emptyset$ in (b). 
 
 \item Third  Case: $P(d)$ is $L(der\,c\,d) = Der\,c\,(L(d))$ (c). We need to treat the cases $d = c$ and $d \not= c$. 
 
@@ -99,8 +99,8 @@
 $\{\texttt{""}\} = \{\texttt{""}\}$ in (c). 
 
 $d \not=c$: We have $der\,c\,d = \ZERO$.
-We also have $Der\,c\,\{\texttt{"}d\texttt{"}\} = \ZERO$. Hence we have 
-$\ZERO = \ZERO$  in (c). 
+We also have $Der\,c\,\{\texttt{"}d\texttt{"}\} = \emptyset$. Hence we have 
+$\emptyset = \emptyset$  in (c). 
 \end{itemize}
 
 \noindent
@@ -192,7 +192,7 @@
 $Der\,c\,(L(r^*)) = Der\,c\,(L(r)^0 \cup \bigcup_{n \ge 1} L(r)^n) = (Der\,c\,L(r)^0) \cup Der\,c\,(\bigcup_{n \ge 1} L(r)^n)$
 \end{center}
 
-The first union ``disappears'' since $Der\,c\,(L(r)^0) = \ZERO$.
+The first union ``disappears'' since $Der\,c\,(L(r)^0) = \emptyset$.
 
 
 \end{document}

Binary file slides/slides04.pdf has changed

--- a/slides/slides04.tex	Tue Oct 31 12:52:36 2023 +0000
+++ b/slides/slides04.tex	Sat Nov 04 18:28:09 2023 +0000
@@ -1737,7 +1737,8 @@
   make the answers public.
 
   $\Rightarrow$ The content viewing numbers are a bit worrying. Therefore
-  the reflex on my side to lecture the content again.
+  the reflex on my side is to lecture the content again. I also receive
+  quite a large number of basic questions about CW2.
 \end{frame}
 
 \begin{frame}[c]
@@ -1768,7 +1769,7 @@
 \item[$\bullet$] This module handout are the most useful thing I have ever seen in this uni.
 \item[$\bullet$] This module is structured very well and is very interesting. Thank you
 \end{itemize}
-$\Rightarrow$ In case of CW3 the starting files are comb1.sc and comb2.sc uploaded to KEATS.
+$\Rightarrow$ In case of CW3 the starting files are comb1.sc and comb2.sc uploaded to KEATS. The CW3 \& 4 files are now on Github. 
 \end{minipage}
 \end{frame}