# HG changeset patch # User Christian Urban # Date 1699122489 0 # Node ID 5e070fb0332a12a13cedf9bd814e848c81e68da3 # Parent 33b3e790e1d4716b14eb96b096f235af41794c43 updated diff -r 33b3e790e1d4 -r 5e070fb0332a hws/hw01.pdf Binary file hws/hw01.pdf has changed diff -r 33b3e790e1d4 -r 5e070fb0332a hws/hw02.pdf Binary file hws/hw02.pdf has changed diff -r 33b3e790e1d4 -r 5e070fb0332a hws/hw03.pdf Binary file hws/hw03.pdf has changed diff -r 33b3e790e1d4 -r 5e070fb0332a hws/hw04.pdf Binary file hws/hw04.pdf has changed diff -r 33b3e790e1d4 -r 5e070fb0332a hws/hw05.pdf Binary file hws/hw05.pdf has changed diff -r 33b3e790e1d4 -r 5e070fb0332a hws/hw05.tex --- 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. diff -r 33b3e790e1d4 -r 5e070fb0332a hws/hw06.pdf Binary file hws/hw06.pdf has changed diff -r 33b3e790e1d4 -r 5e070fb0332a hws/hw07.pdf Binary file hws/hw07.pdf has changed diff -r 33b3e790e1d4 -r 5e070fb0332a hws/hw08.pdf Binary file hws/hw08.pdf has changed diff -r 33b3e790e1d4 -r 5e070fb0332a hws/hw09.pdf Binary file hws/hw09.pdf has changed diff -r 33b3e790e1d4 -r 5e070fb0332a hws/proof.pdf Binary file hws/proof.pdf has changed diff -r 33b3e790e1d4 -r 5e070fb0332a hws/proof.tex --- 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} diff -r 33b3e790e1d4 -r 5e070fb0332a slides/slides04.pdf Binary file slides/slides04.pdf has changed diff -r 33b3e790e1d4 -r 5e070fb0332a slides/slides04.tex --- 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}