Binary file hws/hw04.pdf has changed
--- 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
Binary file slides/slides05.pdf has changed
--- 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}