# HG changeset patch # User Christian Urban # Date 1666944493 -3600 # Node ID 54a483a33763e3c768d69a729ecbb70b9d35fb39 # Parent f4df090a84d07318974f72681bf3c185793887b4 updated diff -r f4df090a84d0 -r 54a483a33763 hws/hw04.pdf Binary file hws/hw04.pdf has changed diff -r f4df090a84d0 -r 54a483a33763 hws/hw04.tex --- a/hws/hw04.tex Fri Oct 21 13:30:12 2022 +0100 +++ b/hws/hw04.tex Fri Oct 28 09:08:13 2022 +0100 @@ -2,6 +2,16 @@ \usepackage{../style} \usepackage{../graphics} +\newcommand{\solution}[1]{% + \begin{quote}\sf% + #1% + \end{quote}} +\renewcommand{\solution}[1]{} + + + + + \begin{document} \section*{Homework 4} @@ -25,7 +35,42 @@ \item If a regular expression $r$ does not contain any occurrence of $\ZERO$, -is it possible for $L(r)$ to be empty? Explain why, or give a proof. + is it possible for $L(r)$ to be empty? Explain why, or give a proof. + + \solution{ + The property to prove is + + \begin{center} + $P(r)$: If $r$ does not contain $\ZERO$, then $L(r) \not= \emptyset$. + \end{center} + + For this you have to now go through all cases. + + Case $r = 0$: $P(\ZERO)$ says: If $\ZERO$ does not contain $\ZERO$ + then \ldots. The premise is obviously false, so everything follows, + in particular $L(r) \not= \emptyset$.\medskip + + Case $r = \ONE$ and $r = c$ are similar, just that the premise is + true, but also $L(\ONE)$ and $L(c)$ are not empty. So we shown + $L(r) \not= \emptyset$.\medskip + + Case $r = r_1 + r_2$: We know $P(r_1)$ and $P(r_2)$ as IHs. We need to show + $P(r_1 + r_2)$: If $r_1 + r_2$ does not contain $\ZERO$, then $L(r_1 + r_2) \not= \emptyset$. + + If $r_1 + r_2$ does not contain $\ZERO$, then also $r_1$ does not contain $\ZERO$ + and $r_2$ does not contain $\ZERO$. So we can apply the two IHs $P(r_1)$ and $P(r_2)$, + which allow us to infer that $L(r_1) \not= \emptyset$ and $L(r_2) \not= \emptyset$. + But if this is the case, then also $L(r_1 + r_2) \not= \emptyset$, which is what we needed + to show in this case.\medskip + + The other cases are similar.\bigskip + + + This lemma essentially says that for basic regular expressions, if + they do not match anything at all, they must contain $\ZERO$(s) + somewhere. + +} \item Define the tokens and regular expressions for a language consisting of numbers, left-parenthesis $($, right-parenthesis $)$, @@ -47,6 +92,19 @@ holds. + \solution{ + If $r$ is nullable, then $1 + r \equiv r$. With this you can replace + + \begin{align} + (1 + r) + r\cdot r & \equiv r + r\cdot r\\ + & \equiv r \cdot (1 + r)\\ + & \equiv r \cdot r + \end{align} + + where in (2) you pull out the ``factor'' $r$ (because $r_1 \cdot (r_2 + r_3) \equiv r_1 \cdot r_2 + r_1 \cdot r_3$). + } + + \item \textbf{(Deleted)} Assume that $s^{-1}$ stands for the operation of reversing a string $s$. Given the following \emph{reversing} function on regular expressions @@ -126,6 +184,66 @@ regular expressions that match some non-empty string), \textit{infinitestrings} (for regular expressions that can match infinitely many strings). + + \solution{ + \textbf{zeroable}: The property is $z(r) \;\text{iff}\; L(r) = \emptyset$: + + \begin{align} + z(\ZERO) &\dn true\\ + z(\ONE) &\dn false\\ + z(c) &\dn false\\ + z(r_1 + r_2) &\dn z(r_1) \wedge z(r_2)\\ + z(r_1 \cdot r_2) &\dn z(r_1) \vee z(r_2)\\ + z(r^*) &\dn false + \end{align}\bigskip + + \textbf{atmostempty}: The property is ``either $L(r) = \emptyset$ or $L(r) = \{[]\}$'', which + is more formally $a(r) \;\text{iff}\; L(r) \subseteq \{[]\}$: + + \begin{align} + a(\ZERO) &\dn true\\ + a(\ONE) &\dn true\\ + a(c) &\dn false\\ + a(r_1 + r_2) &\dn a(r_1) \wedge a(r_2)\\ + a(r_1 \cdot r_2) &\dn z(r_1) \vee z(r_2) \vee (a(r_1) \wedge a(r_2))\\ + a(r^*) &\dn a(r) + \end{align} + + For this it is good to remember the regex should either not + match anything at all, or just the empty string.\bigskip + + \textbf{somechars}: The property is ``$L(r)$ must contain a string which is not the empty string'', which + is more formally $s(r) \;\text{iff}\; \exists\,s. s \not= [] \wedge s \in L(r)$: + + \begin{align} + s(\ZERO) &\dn false\\ + s(\ONE) &\dn false\\ + s(c) &\dn true\\ + s(r_1 + r_2) &\dn s(r_1) \vee s(r_2)\\ + s(r_1 \cdot r_2) &\dn (\neg z(r_1) \wedge s(r_2)) \;\vee\; (\neg z(r_2) \wedge s(r_1))\\ + s(r^*) &\dn s(r) + \end{align} + + Here the interesting case is $r_1 \cdot r_2$ where one essentially has to make sure + that one of the regexes is not zeroable, because then the resulting regex cannot match any + string.\bigskip + + \textbf{infinitestrings}: The property is + $i(r) \;\text{iff}\; L(r)\;\text{is infinite}$: + + \begin{align} + i(\ZERO) &\dn false\\ + i(\ONE) &\dn false\\ + i(c) &\dn false\\ + i(r_1 + r_2) &\dn i(r_1) \vee i(r_2)\\ + i(r_1 \cdot r_2) &\dn (\neg z(r_1) \wedge i(r_2)) \;\vee\; (\neg z(r_2) \wedge i(r_1))\\ + i(r^*) &\dn \neg a(r) + \end{align} + + Here the interesting bit is that as soon $r$ can match at least a single string, then $r^*$ + will match infinitely many strings. + } + \item There are two kinds of automata that are generated for regular expression matching---DFAs and NFAs. (1) Regular expression engines like diff -r f4df090a84d0 -r 54a483a33763 slides/slides05.pdf Binary file slides/slides05.pdf has changed diff -r f4df090a84d0 -r 54a483a33763 slides/slides05.tex --- a/slides/slides05.tex Fri Oct 21 13:30:12 2022 +0100 +++ b/slides/slides05.tex Fri Oct 28 09:08:13 2022 +0100 @@ -30,19 +30,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}