--- a/graphics.sty Thu Jul 30 13:50:54 2020 +0100
+++ b/graphics.sty Sat Aug 15 14:18:37 2020 +0100
@@ -6,16 +6,19 @@
\usetikzlibrary{arrows}
\usetikzlibrary{backgrounds}
\usetikzlibrary{fit}
+\usetikzlibrary{shadows}
\usepackage{tikz-qtree}
\usepackage{graphicx}
\usepackage{pgfplots}
+
+
\pgfplotsset{compat=1.15}
\newenvironment{bubble}[1][]{%
\addtolength{\leftmargini}{4mm}%
\begin{tikzpicture}[baseline=(current bounding box.north)]%
-\draw (0,0) node[inner sep=2mm,fill=cream,ultra thick,draw=red,rounded corners=2mm]%
+\draw (0,0) node[drop shadow,inner sep=2mm,fill=cream,ultra thick,draw=red,rounded corners=2mm]%
\bgroup\begin{minipage}{#1}\raggedright{}}
{\end{minipage}\egroup;%
\end{tikzpicture}\bigskip}
Binary file handouts/graphs.pdf has changed
Binary file handouts/ho01.pdf has changed
--- a/handouts/ho01.tex Thu Jul 30 13:50:54 2020 +0100
+++ b/handouts/ho01.tex Sat Aug 15 14:18:37 2020 +0100
@@ -51,10 +51,10 @@
write into code the machine can run as fast as possible. Developing a
compiler is an old craft going back to 1952 with the first compiler
written by Grace Hopper.\footnote{Who many years ago was invited on a
-talk show hosted by David Letterman, see
-\url{https://youtu.be/3N_ywhx6_K0?t=31}.} Why studying compilers
+talk show hosted by David Letterman.
+\here{https://youtu.be/3N_ywhx6_K0?t=31}.} Why studying compilers
nowadays? An interesting answer is given by John Regher in his compiler
-blog:\footnote{\url{http://blog.regehr.org/archives/1419}}
+blog:\here{http://blog.regehr.org/archives/1419}
\begin{quote}\it{}``We can start off with a couple of observations
about the role of compilers. First, hardware is getting weirder
@@ -107,7 +107,7 @@
program (crashing it or making it go into an infinite loop, if not
worse). This kind of ``inspecting'' mechanism is also implemented in
popular network security tools such as Snort and
-Bro.\footnote{\url{www.snort.org}, \url{www.bro.org}} They scan incoming
+Bro.\here{www.snort.org}\here{www.bro.org} They scan incoming
network traffic for computer viruses or malicious packets. Similarly
filtering out spam usually involves looking for some signature
(essentially a string pattern). The point is that the fast
Binary file handouts/ho02.pdf has changed
Binary file handouts/ho03.pdf has changed
Binary file handouts/ho04.pdf has changed
Binary file handouts/ho05.pdf has changed
Binary file handouts/ho06.pdf has changed
Binary file handouts/ho07.pdf has changed
Binary file handouts/ho08.pdf has changed
Binary file handouts/ho09.pdf has changed
Binary file handouts/ho10.pdf has changed
Binary file handouts/notation.pdf has changed
Binary file handouts/scala-ho.pdf has changed
Binary file hws/hw01.pdf has changed
--- a/hws/hw01.tex Thu Jul 30 13:50:54 2020 +0100
+++ b/hws/hw01.tex Sat Aug 15 14:18:37 2020 +0100
@@ -14,9 +14,15 @@
in the lectures, install the Scala programming language
available (for free) from
-\begin{center}
-\url{http://www.scala-lang.org}
-\end{center}
+ \begin{center}
+ \url{http://www.scala-lang.org}
+ \end{center}
+
+ and the Ammonite REPL from
+
+ \begin{center}
+ \url{https://ammonite.io}
+ \end{center}
If you want to follow the code I present during the
lectures, read the handout about Scala.
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
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/progs/bf/bfi.sc Thu Jul 30 13:50:54 2020 +0100
+++ b/progs/bf/bfi.sc Sat Aug 15 14:18:37 2020 +0100
@@ -47,7 +47,7 @@
case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))
case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))
case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }
- case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte))
+ case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) //scala.io.StdIn.readLine()
case '[' => if (sread(mem, mp) == 0)
(jumpRight(prog, pc + 1, 0), mp, mem)
else (pc + 1, mp, mem)
--- a/slides.sty Thu Jul 30 13:50:54 2020 +0100
+++ b/slides.sty Sat Aug 15 14:18:37 2020 +0100
@@ -1,6 +1,8 @@
\usepackage[absolute,overlay]{textpos}
\usepackage{xcolor}
\usepackage[no-math]{fontspec}
+%%\usepackage{marginnote}
+\usepackage{fontawesome5}
%%%%% CODE FONT
%\setmonofont[Scale=.95]{Consolas}
@@ -24,6 +26,8 @@
\defaultfontfeatures{Ligatures=TeX}
\defaultfontfeatures{Mapping=tex-text}
+%% for recording slides
+\setbeamersize{text margin right=5cm} % <- like this
%%%% Colours
@@ -46,6 +50,12 @@
\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%
\newcommand{\slidecaption}{}
+%%% url pointers
+\newcommand{\here}[1]{\href{#1}{\small\textcolor{ProcessBlue}{\faHandPointRight[regular]}}}
+\newcommand{\video}[1]{\href{#1}{\small\textcolor{ProcessBlue}{\faFilm}}}
+%%\newcommand{\alert}{\reversemarginpar\marginpar{\mbox{}\hfill\textcolor{red}{\faExclamationTriangle}}}
+
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Frametitles
Binary file slides/slides01.pdf has changed
--- a/slides/slides01.tex Thu Jul 30 13:50:54 2020 +0100
+++ b/slides/slides01.tex Sat Aug 15 14:18:37 2020 +0100
@@ -1,10 +1,12 @@
% !TEX program = xelatex
-\documentclass[dvipsnames,14pt,t,xelatex]{beamer}
+\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
\usepackage{../slides}
\usepackage{../graphics}
\usepackage{../langs}
\usepackage{../data}
+
+
\hfuzz=220pt
\lstset{language=Scala,
@@ -24,13 +26,15 @@
\begin{document}
+
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Compilers and \\[-1mm]
- \LARGE Formal Languages (1)\\[-3mm]
+ \LARGE Formal Languages\\[-3mm]
\end{tabular}}
\begin{center}
@@ -43,12 +47,28 @@
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
- Office Hours: & Thursdays 12 -- 14\\
- Location: & N7.07 (North Wing, Bush House)\\
+ %Office Hours: & Thursdays 12 -- 14\\
+ %Location: & N7.07 (North Wing, Bush House)\\
Slides \& Progs: & KEATS\\
\end{tabular}
\end{center}
+ \begin{center}
+ \begin{tikzpicture}
+ \node[drop shadow,fill=white,inner sep=0pt]
+ {\footnotesize\rowcolors{1}{capri!10}{white}
+ \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
+ \cellcolor{blue!50}
+ 1 Introduction, Languages & 6 While-Language \\
+ 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
+ 3 Automata, Regular Languages & 8 Compiling Functional Languages \\
+ 4 Lexing, Tokenising & 9 Optimisations \\
+ 5 Grammars, Parsing & 10 LLVM \\ \hline
+ \end{tabular}%
+ };
+ \end{tikzpicture}
+ \end{center}
+
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -56,7 +76,10 @@
\begin{frame}[t]
\frametitle{Why Study Compilers?}
-John Regehr {\small(Univ.~Utah, LLVM compiler hacker)}\smallskip\\
+
+John Regehr {\small(Univ.~Utah, LLVM compiler hacker)}
+\here{https://blog.regehr.org/archives/1419}
+\smallskip\\
\begin{bubble}[10.5cm]
\bf ``\ldots{}It’s effectively a perpetual
@@ -104,12 +127,12 @@
\node (1) [right=35mm] at (0) {\includegraphics[scale=0.3]{pics/cassmbl.png}};
\draw [->,line width=4mm, red] (0) -- (1);
\node (2) [below=25mm] at (0) {\LARGE\bf``source''};
- \node (3) [right=35mm] at (2) {\LARGE\bf``binary''};
+ \node (3) [right=40mm] at (2) {\LARGE\bf``binary''};
\draw [->,line width=1mm] (2) -- (3);
\end{tikzpicture}
\end{center}
-\begin{textblock}{10}(1,13.5)
+\begin{textblock}{12}(1,14.5)
Compiler explorers, e.g.: \url{https://gcc.godbolt.org}
\end{textblock}
@@ -296,7 +319,7 @@
node/.style={
rectangle,rounded corners=3mm,
very thick,draw=black!50,minimum height=18mm, minimum width=20mm,
- top color=white,bottom color=black!20}]
+ top color=white,bottom color=black!20,drop shadow}]
\node at (3.05, 1.8) {\Large\bf write a compiler};
@@ -473,7 +496,7 @@
\end{tabular}
\end{center}\bigskip
- \texttt{char field[30000]\\ char *ptr = &field[15000]}
+ \texttt{char field[30000]\\ char *ptr = \&field[15000]}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -956,6 +979,110 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
+\frametitle{Languages (Sets of Strings)}
+
+\begin{itemize}
+
+\item A \alert{\bf Language} is a set of strings, for example\medskip
+\begin{center}
+\bl{$\{[], hello, foobar, a, abc\}$}
+\end{center}\bigskip
+
+\item \alert{\bf Concatenation} for strings and languages
+
+\begin{center}
+\begin{tabular}{rcl}
+\bl{$foo\;@\;bar$} & \bl{$=$} & \bl{$foobar$}\medskip\\
+\bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$}
+\end{tabular}
+\end{center}
+\bigskip
+
+\small
+\item [] For example \bl{$A = \{foo, bar\}$}, \bl{$B = \{a, b\}$}
+
+\[
+\bl{A \,@\, B = \{fooa, foob, bara, barb\}}
+\]
+
+\end{itemize}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+ \frametitle{Two Corner Cases}
+
+ \Large
+ \begin{center}
+ \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\
+ \bl{$A \,@\, \{\} = \;?$}
+ \end{center}
+
+ \end{frame}
+ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{
+ The Meaning of a\\[-2mm]
+ Regular Expression}
+
+ ...all the strings a regular expression can match.
+
+\begin{center}
+ \begin{tabular}{rcl}
+ \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\
+ \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\
+ \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\
+ \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
+ \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\
+ \bl{$L(r^*)$} & \bl{$\dn$} & \\
+ \end{tabular}
+\end{center}
+
+\begin{textblock}{14}(1.5,13.5)\small
+\bl{$L$} is a function from regular expressions to
+sets of strings (languages):\smallskip\\
+\bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{The Power Operation}
+
+\begin{itemize}
+\item The \alert{\textbf{\boldmath$n$th Power}} of a language:
+
+\begin{center}
+\begin{tabular}{lcl}
+\bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\
+\bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$}
+\end{tabular}
+\end{center}\bigskip
+
+\item[] For example
+
+\begin{center}
+\begin{tabular}{lcl@{\hspace{10mm}}l}
+\bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\
+\bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\
+\bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\
+\end{tabular}
+\end{center}
+
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
\frametitle{The Star Operation}
\begin{itemize}
Binary file slides/slides02.pdf has changed
--- a/slides/slides02.tex Thu Jul 30 13:50:54 2020 +0100
+++ b/slides/slides02.tex Sat Aug 15 14:18:37 2020 +0100
@@ -1,5 +1,5 @@
% !TEX program = xelatex
-\documentclass[dvipsnames,14pt,t]{beamer}
+\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
\usepackage{../slides}
\usepackage{../graphics}
\usepackage{../langs}
@@ -29,26 +29,42 @@
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Compilers and \\[-1mm]
- \LARGE Formal Languages (2)\\[3mm]
+ \LARGE Formal Languages\\[3mm]
\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)\\
+ %Office Hours: & Thursdays 12 -- 14\\
+ %Location: & N7.07 (North Wing, Bush House)\\
Slides \& Progs: & KEATS (also homework is there)\\
\end{tabular}
\end{center}
+ \begin{center}
+ \begin{tikzpicture}
+ \node[drop shadow,fill=white,inner sep=0pt]
+ {\footnotesize\rowcolors{1}{capri!10}{white}
+ \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
+ 1 Introduction, Languages & 6 While-Language \\
+ \cellcolor{blue!50}
+ 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
+ 3 Automata, Regular Languages & 8 Compiling Functional Languages \\
+ 4 Lexing, Tokenising & 9 Optimisations \\
+ 5 Grammars, Parsing & 10 LLVM \\ \hline
+ \end{tabular}%
+ };
+ \end{tikzpicture}
+ \end{center}
+
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{
- Lets Implement an Efficient\\[-2mm]
+ Let's Implement an Efficient\\[-2mm]
Regular Expression Matcher}
\footnotesize
@@ -149,193 +165,7 @@
\end{center}
\vspace{\fill}
-Q: \;What about \;\bl{$r \cdot 0$} \; ?
-\end{frame}
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Languages (Sets of Strings)}
-
-\begin{itemize}
-
-\item A \alert{\bf Language} is a set of strings, for example\medskip
-\begin{center}
-\bl{$\{[], hello, foobar, a, abc\}$}
-\end{center}\bigskip
-
-\item \alert{\bf Concatenation} for strings and languages
-
-\begin{center}
-\begin{tabular}{rcl}
-\bl{$foo\;@\;bar$} & \bl{$=$} & \bl{$foobar$}\medskip\\
-\bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$}
-\end{tabular}
-\end{center}
-\bigskip
-
-\small
-\item [] For example \bl{$A = \{foo, bar\}$}, \bl{$B = \{a, b\}$}
-
-\[
-\bl{A \,@\, B = \{fooa, foob, bara, barb\}}
-\]
-
-\end{itemize}
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
- \frametitle{Two Corner Cases}
-
- \Large
- \begin{center}
- \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\
- \bl{$A \,@\, \{\} = \;?$}
- \end{center}
-
- \end{frame}
- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{
- The Meaning of a\\[-2mm]
- Regular Expression}
-
- ...all the strings a regular expression can match.
-
-\begin{center}
- \begin{tabular}{rcl}
- \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\
- \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\
- \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\
- \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
- \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\
- \bl{$L(r^*)$} & \bl{$\dn$} & \\
- \end{tabular}
-\end{center}
-
-\begin{textblock}{14}(1.5,13.5)\small
-\bl{$L$} is a function from regular expressions to
-sets of strings (languages):\smallskip\\
-\bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
-\end{textblock}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{The Power Operation}
-
-\begin{itemize}
-\item The \alert{\textbf{\boldmath$n$th Power}} of a language:
-
-\begin{center}
-\begin{tabular}{lcl}
-\bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\
-\bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$}
-\end{tabular}
-\end{center}\bigskip
-
-\item[] For example
-
-\begin{center}
-\begin{tabular}{lcl@{\hspace{10mm}}l}
-\bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\
-\bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\
-\bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\
-\end{tabular}
-\end{center}
-
-\end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
- \frametitle{Homework Question}
-
- \begin{itemize}
- \item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip
-
- \item[]
- How many strings are in \bl{$A^4$}\,?
- \bigskip\medskip\pause
-
-
- \item[]
- What if \bl{$A = \{[a],[b],[c],[]\}$};\\
- how many strings are then in \bl{$A^4$}\,?
- \end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{The Star Operation}
-
-\begin{itemize}
-\item The \alert{\bf Kleene Star} of a \underline{language}:
-\bigskip
-
-\begin{center}
-\begin{tabular}{c}
-\bl{$A\star \dn \bigcup_{0\le n} A^n$}
-\end{tabular}
-\end{center}\bigskip
-
-\item[] This expands to
-
-\[
-\bl{A^0 \cup A^1 \cup A^2 \cup A^3 \cup A^4 \cup \ldots}
-\]
-
-or
-
-\small
-\[
-\bl{\{[]\} \;\cup\; A \;\cup\; A\,@\,A \;\cup\;
- A\,@\,A\,@\,A \;\cup\; A\,@\,A\,@\,A\,@\,A \cup \ldots}
-\]
-
-\end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{
- The Meaning of a\\[-2mm]
- Regular Expression}
-
-...all the strings a regular expression can match.
-
-\begin{center}
- \begin{tabular}{rcl}
- \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\
- \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\
- \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\
- \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
- \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\
- \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star \quad\dn \bigcup_{0 \le n} L(r)^n$}\\
- \end{tabular}
-\end{center}
-
-%\begin{textblock}{9}(6,12)\small
-%\bl{$L$} is a function from regular expressions to
-%sets of strings (languages):\smallskip\\
-%\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
-%\end{textblock}
-
+%%Q: \;What about \;\bl{$r \cdot 0$} \; ?
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -435,17 +265,6 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}\\[3cm]\huge\alert{Questions?}\end{tabular}}
-
-\bigskip
-homework (written exam 80\%)\\
-coursework (20\%; first one today)\\
-submission Fridays @ 18:00 -- accepted until Mondays
-\mbox{}
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -812,9 +631,7 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
- \frametitle{
- Another Example\\[-2mm]
- in Java 8, Python and JavaScript}
+ \frametitle{Another Example \boldmath$(a^*)^* \cdot b$}
\bigskip
\begin{center}
@@ -1220,7 +1037,223 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}\\[3cm]\huge\alert{Questions?}\end{tabular}}
+
+\bigskip
+homework (written exam 80\%)\\
+coursework (20\%; first one today)\\
+submission Fridays @ 18:00 -- accepted until Mondays
+\mbox{}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Last Week}
+
+Last week I showed you a regular expression matcher
+that works provably correct in all cases (we only
+started with the proving part though)
+
+\begin{center}
+\bl{$matches\,s\,r$} \;\;if and only if \;\; \bl{$s \in L(r)$}
+\end{center}\bigskip\bigskip
+
+\small
+\textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{The Derivative of a Rexp}
+
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
+ \bl{$der\, c\, (\ZERO)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
+ \bl{$der\, c\, (\ONE)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
+ \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\
+ \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\
+ \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\
+ & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\
+ & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\
+ \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\
+
+ \bl{$\textit{ders}\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\
+ \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\
+ \end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Example}
+
+Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
+
+\begin{center}
+\def\arraystretch{1.5}
+\begin{tabular}{@{}lcl}
+ \bl{$\der\,a\,((a \cdot b) + b)^*$}
+ & \bl{$\Rightarrow$}& \bl{$\der\,a\, \underline{((a \cdot b) + b)^*}$}\\
+ & \bl{$=$} & \bl{$(der\,a\,(\underline{(a \cdot b) + b})) \cdot r$}\\
+ & \bl{$=$} & \bl{$((der\,a\,(\underline{a \cdot b})) + (der\,a\,b)) \cdot r$}\\
+ & \bl{$=$} & \bl{$(((der\,a\,\underline{a}) \cdot b) + (der\,a\,b)) \cdot r$}\\
+ & \bl{$=$} & \bl{$((\ONE \cdot b) + (der\,a\,\underline{b})) \cdot r$}\\
+ & \bl{$=$} & \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+Input: string \bl{$abc$} and regular expression \bl{$r$}
+
+\begin{enumerate}
+\item \bl{$der\,a\,r$}
+\item \bl{$der\,b\,(der\,a\,r)$}
+\item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause
+\item finally check whether the last regular expression can match the empty string
+\end{enumerate}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Simplification}
+
+Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows
+
+\begin{center}
+\def\arraystretch{2}
+\begin{tabular}{@{}lcl}
+ \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}
+ & \bl{$\Rightarrow$} & \bl{$((\underline{\ONE \cdot b}) + \ZERO) \cdot r$}\\
+ & \bl{$=$} & \bl{$(\underline{b + \ZERO}) \cdot r$}\\
+ & \bl{$=$} & \bl{$b \cdot r$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+ \frametitle{Proofs about Rexp}
+
+ \begin{itemize}
+ \item \bl{$P$} holds for \bl{$\ZERO$}, \bl{$\ONE$} and \bl{c}\bigskip
+ \item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already
+ holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip
+ \item \bl{$P$} holds for \bl{$r_1 \cdot r_2$} under the assumption that \bl{$P$} already
+ holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip
+ \item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already
+ holds for \bl{$r$}.
+ \end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+We proved
+
+\begin{center}
+\bl{$nullable(r)$} \;if and only if\; \bl{$[] \in L(r)$}
+\end{center}
+
+by induction on the regular expression \bl{$r$}.\bigskip\pause
+
+\begin{center}
+{\huge\bf\alert{Any Questions?}}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Proofs about Natural\\[-1mm] Numbers and Strings\end{tabular}}
+
+\begin{itemize}
+\item \bl{$P$} holds for \bl{$0$} and
+\item \bl{$P$} holds for \bl{$n + 1$} under the assumption that \bl{$P$} already
+holds for \bl{$n$}
+\end{itemize}\bigskip
+
+\begin{itemize}
+\item \bl{$P$} holds for \bl{$[]$} and
+\item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already
+holds for \bl{$s$}
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+ \frametitle{Correctness Proof \\[-1mm]
+ for our Matcher}
+
+ \begin{itemize}
+ \item We started from
+
+ \begin{center}
+ \begin{tabular}{rp{4cm}}
+ & \bl{$s \in L(r)$}\medskip\\
+ \bl{$\Leftrightarrow$} & \bl{$[] \in \Ders\,s\,(L(r))$}\pause
+ \end{tabular}
+ \end{center}\bigskip
+
+ \item \textbf{\alert{if}} we can show \bl{$\Ders\, s\,(L(r)) = L(\ders\,s\,r)$} we
+ have\bigskip
+
+ \begin{center}
+ \begin{tabular}{rp{4cm}}
+ \bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\
+ \bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\
+ \bl{$\dn$} & \bl{$matches\,s\,r$}
+ \end{tabular}
+ \end{center}
+
+ \end{itemize}
+
+ \end{frame}
+ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+We need to prove
+
+\begin{center}
+\bl{$L(der\,c\,r) = Der\,c\,(L(r))$}
+\end{center}
+
+also by induction on the regular expression \bl{$r$}.
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
\end{document}
Binary file slides/slides03.pdf has changed
--- a/slides/slides03.tex Thu Jul 30 13:50:54 2020 +0100
+++ b/slides/slides03.tex Sat Aug 15 14:18:37 2020 +0100
@@ -1,5 +1,5 @@
% !TEX program = xelatex
-\documentclass[dvipsnames,14pt,t]{beamer}
+\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
\usepackage{../slides}
\usepackage{../graphics}
\usepackage{../langs}
@@ -22,17 +22,33 @@
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Compilers and \\[-2mm]
- \LARGE Formal Languages (3)\\[3mm]
+ \LARGE Formal Languages\\[3mm]
\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)\\
+ %Office Hours: & Thursdays 12 -- 14\\
+ %Location: & N7.07 (North Wing, Bush House)\\
Slides \& Progs: & KEATS (also homework is there)\\
\end{tabular}
+\end{center}
+
+ \begin{center}
+ \begin{tikzpicture}
+ \node[drop shadow,fill=white,inner sep=0pt]
+ {\footnotesize\rowcolors{1}{capri!10}{white}
+ \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
+ 1 Introduction, Languages & 6 While-Language \\
+ 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
+ \cellcolor{blue!50}
+ 3 Automata, Regular Languages & 8 Compiling Functional Languages \\
+ 4 Lexing, Tokenising & 9 Optimisations \\
+ 5 Grammars, Parsing & 10 LLVM \\ \hline
+ \end{tabular}%
+ };
+ \end{tikzpicture}
\end{center}
\end{frame}
@@ -55,206 +71,6 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Last Week}
-
-Last week I showed you a regular expression matcher
-that works provably correct in all cases (we only
-started with the proving part though)
-
-\begin{center}
-\bl{$matches\,s\,r$} \;\;if and only if \;\; \bl{$s \in L(r)$}
-\end{center}\bigskip\bigskip
-
-\small
-\textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{The Derivative of a Rexp}
-
-\begin{center}
-\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
- \bl{$der\, c\, (\ZERO)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
- \bl{$der\, c\, (\ONE)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
- \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\
- \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\
- \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\
- & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\
- & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\
- \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\
-
- \bl{$\textit{ders}\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\
- \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\
- \end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Example}
-
-Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
-
-\begin{center}
-\def\arraystretch{1.5}
-\begin{tabular}{@{}lcl}
- \bl{$\der\,a\,((a \cdot b) + b)^*$}
- & \bl{$\Rightarrow$}& \bl{$\der\,a\, \underline{((a \cdot b) + b)^*}$}\\
- & \bl{$=$} & \bl{$(der\,a\,(\underline{(a \cdot b) + b})) \cdot r$}\\
- & \bl{$=$} & \bl{$((der\,a\,(\underline{a \cdot b})) + (der\,a\,b)) \cdot r$}\\
- & \bl{$=$} & \bl{$(((der\,a\,\underline{a}) \cdot b) + (der\,a\,b)) \cdot r$}\\
- & \bl{$=$} & \bl{$((\ONE \cdot b) + (der\,a\,\underline{b})) \cdot r$}\\
- & \bl{$=$} & \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}\\
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-
-Input: string \bl{$abc$} and regular expression \bl{$r$}
-
-\begin{enumerate}
-\item \bl{$der\,a\,r$}
-\item \bl{$der\,b\,(der\,a\,r)$}
-\item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause
-\item finally check whether the last regular expression can match the empty string
-\end{enumerate}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{Simplification}
-
-Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows
-
-\begin{center}
-\def\arraystretch{2}
-\begin{tabular}{@{}lcl}
- \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}
- & \bl{$\Rightarrow$} & \bl{$((\underline{\ONE \cdot b}) + \ZERO) \cdot r$}\\
- & \bl{$=$} & \bl{$(\underline{b + \ZERO}) \cdot r$}\\
- & \bl{$=$} & \bl{$b \cdot r$}\\
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
- \frametitle{Proofs about Rexp}
-
- \begin{itemize}
- \item \bl{$P$} holds for \bl{$\ZERO$}, \bl{$\ONE$} and \bl{c}\bigskip
- \item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already
- holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip
- \item \bl{$P$} holds for \bl{$r_1 \cdot r_2$} under the assumption that \bl{$P$} already
- holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip
- \item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already
- holds for \bl{$r$}.
- \end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-
-We proved
-
-\begin{center}
-\bl{$nullable(r)$} \;if and only if\; \bl{$[] \in L(r)$}
-\end{center}
-
-by induction on the regular expression \bl{$r$}.\bigskip\pause
-
-\begin{center}
-{\huge\bf\alert{Any Questions?}}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Proofs about Natural\\[-1mm] Numbers and Strings\end{tabular}}
-
-\begin{itemize}
-\item \bl{$P$} holds for \bl{$0$} and
-\item \bl{$P$} holds for \bl{$n + 1$} under the assumption that \bl{$P$} already
-holds for \bl{$n$}
-\end{itemize}\bigskip
-
-\begin{itemize}
-\item \bl{$P$} holds for \bl{$[]$} and
-\item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already
-holds for \bl{$s$}
-\end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
- \frametitle{Correctness Proof \\[-1mm]
- for our Matcher}
-
- \begin{itemize}
- \item We started from
-
- \begin{center}
- \begin{tabular}{rp{4cm}}
- & \bl{$s \in L(r)$}\medskip\\
- \bl{$\Leftrightarrow$} & \bl{$[] \in \Ders\,s\,(L(r))$}\pause
- \end{tabular}
- \end{center}\bigskip
-
- \item \textbf{\alert{if}} we can show \bl{$\Ders\, s\,(L(r)) = L(\ders\,s\,r)$} we
- have\bigskip
-
- \begin{center}
- \begin{tabular}{rp{4cm}}
- \bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\
- \bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\
- \bl{$\dn$} & \bl{$matches\,s\,r$}
- \end{tabular}
- \end{center}
-
- \end{itemize}
-
- \end{frame}
- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-
-We need to prove
-
-\begin{center}
-\bl{$L(der\,c\,r) = Der\,c\,(L(r))$}
-\end{center}
-
-also by induction on the regular expression \bl{$r$}.
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{(Basic) Regular Expressions}
@@ -1329,6 +1145,360 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{center}
+\begin{tikzpicture}[scale=2,>=stealth',very thick,
+ every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
+ \only<-7>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};}
+ \only<8->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};}
+ \only<-7>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};}
+ \only<8->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};}
+ \node[state] (q2) at ( 2,1) {$\mbox{Q}_2$};
+ \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
+ (q1) edge[bend left] node[above] {\alert{$b$}} (q0)
+ (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
+ (q1) edge node[above] {\alert{$a$}} (q2)
+ (q2) edge [loop right] node {\alert{$a$}} ()
+ (q0) edge [loop below] node {\alert{$b$}} ()
+ ;
+\end{tikzpicture}
+\end{center}\bigskip
+
+\begin{center}
+\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b + \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\
+\end{tabular}
+\end{center}
+
+
+Arden's Lemma:
+\begin{center}
+If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
+\end{center}
+
+\only<2-6>{\small
+\begin{textblock}{6}(1,0.8)
+\begin{bubble}[6.7cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+\multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} \& \bl{$\mbox{Q}_2$}:}\\
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b + \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<3-6>{\small
+\begin{textblock}{6}(2,4.15)
+\begin{bubble}[6.7cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+\multicolumn{3}{@{}l}{simplifying \bl{$\mbox{Q}_0$}:}\\
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<4-6>{\small
+\begin{textblock}{6}(3,7.55)
+\begin{bubble}[6.7cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+ \multicolumn{3}{@{}l}{Arden for \bl{$\mbox{Q}_2$}:}\\
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$}
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<5-6>{\small
+\begin{textblock}{6}(4,10.9)
+\begin{bubble}[7.5cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+ \multicolumn{3}{@{}l}{Substitute \bl{$\mbox{Q}_2$} and simplify:}\\
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b)$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<6>{\small
+\begin{textblock}{6}(5,13.4)
+\begin{bubble}[7.5cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+ \multicolumn{3}{@{}l}{Arden again for \bl{$\mbox{Q}_0$}:}\\
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+
+\only<7->{\small
+\begin{textblock}{6}(6,11.5)
+\begin{bubble}[6.7cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+\multicolumn{3}{@{}l}{Finally:}\\
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\
+\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a^*)$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Regexps and Automata}
+
+\begin{center}
+\begin{tikzpicture}
+\node (rexp) {\bl{\bf Regexps}};
+\node (nfa) [right=of rexp] {\bl{\bf NFAs}};
+\node (dfa) [right=of nfa] {\bl{\bf DFAs}};
+\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}};
+\path[->,red, line width=2mm] (rexp) edge node [above=4mm, black]
+ {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa);
+\path[->,red, line width=2mm] (nfa) edge node [above=4mm, black]
+ {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa);
+\path[->, red, line width=2mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa);
+%%\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp);
+\path[->, red, line width=2mm] (dfa) edge [bend left=45] node [below, black] {\begin{tabular}{l}Brzozowski's\\ method\end{tabular}} (rexp);
+
+\end{tikzpicture}\\
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}}
+
+\begin{tikzpicture}
+\begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,5,...,30},
+ xmax=30,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=10cm,
+ height=7cm,
+ legend entries={Python,Ruby,my NFA},
+ legend pos=north west,
+ legend cell align=left]
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
+\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data};
+\addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data};
+\end{axis}
+\end{tikzpicture}
+
+The punchline is that many existing libraries do depth-first search
+in NFAs (backtracking).
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% \begin{frame}[c]
+% \frametitle{DFA to Rexp}
+
+% \begin{center}
+% \begin{tikzpicture}[scale=2,>=stealth',very thick,
+% every state/.style={minimum size=0pt,
+% draw=blue!50,very thick,fill=blue!20},]
+% \node[state, initial] (q0) at ( 0,1) {$q_0$};
+% \node[state] (q1) at ( 1,1) {$q_1$};
+% \node[state, accepting] (q2) at ( 2,1) {$q_2$};
+% \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
+% (q1) edge[bend left] node[above] {\alert{$b$}} (q0)
+% (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
+% (q1) edge node[above] {\alert{$a$}} (q2)
+% (q2) edge [loop right] node {\alert{$a$}} ()
+% (q0) edge [loop below] node {\alert{$b$}} ();
+% \end{tikzpicture}
+% \end{center}\bigskip
+
+% \begin{center}
+% \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l}
+% \bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b + q_2\,b$} & (start state)\\
+% \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\
+% \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\
+
+% \end{tabular}
+% \end{center}
+
+% Arden's Lemma:
+% \begin{center}
+% If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
+% \end{center}
+
+
+% \end{frame}
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% \begin{frame}[c]
+% \frametitle{DFA Minimisation}
+
+% \begin{enumerate}
+% \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$}
+% \item Mark all pairs that accepting and non-accepting states
+% \item For all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether
+% \begin{center}
+% \bl{$(\delta(q, c), \delta(p,c))$}
+% \end{center}
+% are marked. If yes, then also mark \bl{$(q, p)$}.
+% \item Repeat last step until no change.
+% \item All unmarked pairs can be merged.
+% \end{enumerate}
+
+% \end{frame}
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% \begin{frame}[c]
+
+% \begin{center}
+% \begin{tabular}{@{\hspace{-8mm}}cc@{}}
+% \begin{tikzpicture}[>=stealth',very thick,auto,
+% every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]
+% \node[state,initial] (q_0) {$q_0$};
+% \node[state] (q_1) [right=of q_0] {$q_1$};
+% \node[state] (q_2) [below right=of q_0] {$q_2$};
+% \node[state] (q_3) [right=of q_2] {$q_3$};
+% \node[state, accepting] (q_4) [right=of q_1] {$q_4$};
+% \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1);
+% \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4);
+% \path[->] (q_4) edge [loop right] node {\alert{$a, b$}} ();
+% \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4);
+% \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3);
+% \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2);
+% \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2);
+% \path[->] (q_2) edge [loop left] node {\alert{$b$}} ();
+% \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);
+% \end{tikzpicture}
+% &
+% \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm]
+% \draw (0,0) -- (4,0);
+% \draw (0,1) -- (4,1);
+% \draw (0,2) -- (3,2);
+% \draw (0,3) -- (2,3);
+% \draw (0,4) -- (1,4);
+
+% \draw (0,0) -- (0, 4);
+% \draw (1,0) -- (1, 4);
+% \draw (2,0) -- (2, 3);
+% \draw (3,0) -- (3, 2);
+% \draw (4,0) -- (4, 1);
+
+% \draw (0.5,-0.5) node {$q_0$};
+% \draw (1.5,-0.5) node {$q_1$};
+% \draw (2.5,-0.5) node {$q_2$};
+% \draw (3.5,-0.5) node {$q_3$};
+
+% \draw (-0.5, 3.5) node {$q_1$};
+% \draw (-0.5, 2.5) node {$q_2$};
+% \draw (-0.5, 1.5) node {$q_3$};
+% \draw (-0.5, 0.5) node {$q_4$};
+
+% \draw (0.5,0.5) node {\large$\star$};
+% \draw (1.5,0.5) node {\large$\star$};
+% \draw (2.5,0.5) node {\large$\star$};
+% \draw (3.5,0.5) node {\large$\star$};
+% \draw (0.5,1.5) node {\large$\star$};
+% \draw (2.5,1.5) node {\large$\star$};
+% \draw (0.5,3.5) node {\large$\star$};
+% \draw (1.5,2.5) node {\large$\star$};
+% \end{tikzpicture}}
+% \end{tabular}
+% \end{center}
+
+
+% \mbox{}\\[-20mm]\mbox{}
+
+% \begin{center}
+% \begin{tikzpicture}[>=stealth',very thick,auto,
+% every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]
+% \node[state,initial] (q_02) {$q_{0, 2}$};
+% \node[state] (q_13) [right=of q_02] {$q_{1, 3}$};
+% \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$};
+% \path[->] (q_02) edge [bend left] node [above] {\alert{$a$}} (q_13);
+% \path[->] (q_13) edge [bend left] node [below] {\alert{$b$}} (q_02);
+% \path[->] (q_02) edge [loop below] node {\alert{$b$}} ();
+% \path[->] (q_13) edge node [above] {\alert{$a$}} (q_4);
+% \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} ();
+% \end{tikzpicture}\\
+% minimal automaton
+% \end{center}
+
+% \end{frame}
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Regular Languages}
+
+Two equivalent definitions:\bigskip
+
+\begin{quote}\rm A language is \alert{regular} iff there exists a
+regular expression that recognises all its strings.
+\end{quote}
+
+\begin{quote}\rm A language is \alert{regular} iff there exists an
+automaton that recognises all its strings.
+\end{quote}\bigskip\bigskip
+
+
+\small
+for example \bl{$a^nb^n$} is not regular
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Negation}
+
+Regular languages are closed under negation:\bigskip
+
+\begin{center}
+\begin{tikzpicture}[scale=2,>=stealth',very thick,
+ every state/.style={minimum size=0pt,
+ draw=blue!50,very thick,fill=blue!20}]
+ \only<1>{\node[state,initial] (q0) at ( 0,1) {$q_0$};}
+ \only<2>{\node[state,initial,accepting] (q0) at ( 0,1) {$q_0$};}
+ \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};}
+ \only<2>{\node[state,accepting] (q1) at ( 1,1) {$q_1$};}
+ \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};}
+ \only<2>{\node[state] (q2) at ( 2,1) {$q_2$};}
+ \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
+ (q1) edge[bend left] node[above] {\alert{$b$}} (q0)
+ (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
+ (q1) edge node[above] {\alert{$a$}} (q2)
+ (q2) edge [loop right] node {\alert{$a$}} ()
+ (q0) edge [loop below] node {\alert{$b$}} ();
+\end{tikzpicture}
+\end{center}\bigskip\bigskip
+
+But requires that the automaton is \alert{completed}!
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
\end{document}
%%% Local Variables:
Binary file slides/slides04.pdf has changed
--- a/slides/slides04.tex Thu Jul 30 13:50:54 2020 +0100
+++ b/slides/slides04.tex Sat Aug 15 14:18:37 2020 +0100
@@ -1,5 +1,5 @@
% !TEX program = xelatex
-\documentclass[dvipsnames,14pt,t]{beamer}
+\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
\usepackage{../slides}
\usepackage{../graphics}
\usepackage{../langs}
@@ -27,126 +27,38 @@
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Compilers and \\[-2mm]
- \LARGE Formal Languages (4)\\[3mm]
+ \LARGE Formal Languages\\[3mm]
\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)\\
+ %Office Hours: & Thursdays 12 -- 14\\
+ %Location: & N7.07 (North Wing, Bush House)\\
Slides \& Progs: & KEATS (also homework is there)\\
\end{tabular}
\end{center}
+
+ \begin{center}
+ \begin{tikzpicture}
+ \node[drop shadow,fill=white,inner sep=0pt]
+ {\footnotesize\rowcolors{1}{capri!10}{white}
+ \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
+ 1 Introduction, Languages & 6 While-Language \\
+ 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
+ 3 Automata, Regular Languages & 8 Compiling Functional Languages \\
+ \cellcolor{blue!50}
+ 4 Lexing, Tokenising & 9 Optimisations \\
+ 5 Grammars, Parsing & 10 LLVM \\ \hline
+ \end{tabular}%
+ };
+ \end{tikzpicture}
+ \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-
-\begin{center}
-\begin{tikzpicture}[scale=2,>=stealth',very thick,
- every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
- \only<-7>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};}
- \only<8->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};}
- \only<-7>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};}
- \only<8->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};}
- \node[state] (q2) at ( 2,1) {$\mbox{Q}_2$};
- \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
- (q1) edge[bend left] node[above] {\alert{$b$}} (q0)
- (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
- (q1) edge node[above] {\alert{$a$}} (q2)
- (q2) edge [loop right] node {\alert{$a$}} ()
- (q0) edge [loop below] node {\alert{$b$}} ()
- ;
-\end{tikzpicture}
-\end{center}\bigskip
-
-\begin{center}
-\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
-\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b + \mbox{Q}_2\,b$}\\
-\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\
-\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\
-\end{tabular}
-\end{center}
-
-
-Arden's Lemma:
-\begin{center}
-If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
-\end{center}
-
-\only<2-6>{\small
-\begin{textblock}{6}(1,0.8)
-\begin{bubble}[6.7cm]
-\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
-\multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} \& \bl{$\mbox{Q}_2$}:}\\
-\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b + \mbox{Q}_2\,b$}\\
-\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}
-\end{tabular}
-\end{bubble}
-\end{textblock}}
-
-\only<3-6>{\small
-\begin{textblock}{6}(2,4.15)
-\begin{bubble}[6.7cm]
-\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
-\multicolumn{3}{@{}l}{simplifying \bl{$\mbox{Q}_0$}:}\\
-\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\
-\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}
-\end{tabular}
-\end{bubble}
-\end{textblock}}
-
-\only<4-6>{\small
-\begin{textblock}{6}(3,7.55)
-\begin{bubble}[6.7cm]
-\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
- \multicolumn{3}{@{}l}{Arden for \bl{$\mbox{Q}_2$}:}\\
-\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\
-\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$}
-\end{tabular}
-\end{bubble}
-\end{textblock}}
-
-\only<5-6>{\small
-\begin{textblock}{6}(4,10.9)
-\begin{bubble}[7.5cm]
-\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
- \multicolumn{3}{@{}l}{Substitute \bl{$\mbox{Q}_2$} and simplify:}\\
-\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b)$}\\
-\end{tabular}
-\end{bubble}
-\end{textblock}}
-
-\only<6>{\small
-\begin{textblock}{6}(5,13.4)
-\begin{bubble}[7.5cm]
-\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
- \multicolumn{3}{@{}l}{Arden again for \bl{$\mbox{Q}_0$}:}\\
-\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\
-\end{tabular}
-\end{bubble}
-\end{textblock}}
-
-
-\only<7->{\small
-\begin{textblock}{6}(6,11.5)
-\begin{bubble}[6.7cm]
-\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
-\multicolumn{3}{@{}l}{Finally:}\\
-\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\
-\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a$}\\
-\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a^*)$}\\
-\end{tabular}
-\end{bubble}
-\end{textblock}}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
@@ -192,251 +104,7 @@
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Regexps and Automata}
-
-\begin{center}
-\begin{tikzpicture}
-\node (rexp) {\bl{\bf Regexps}};
-\node (nfa) [right=of rexp] {\bl{\bf NFAs}};
-\node (dfa) [right=of nfa] {\bl{\bf DFAs}};
-\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}};
-\path[->,red, line width=2mm] (rexp) edge node [above=4mm, black]
- {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa);
-\path[->,red, line width=2mm] (nfa) edge node [above=4mm, black]
- {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa);
-\path[->, red, line width=2mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa);
-%%\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp);
-\path[->, red, line width=2mm] (dfa) edge [bend left=45] node [below, black] {\begin{tabular}{l}Brzozowski's\\ method\end{tabular}} (rexp);
-
-\end{tikzpicture}\\
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}}
-
-\begin{tikzpicture}
-\begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs},
- enlargelimits=false,
- xtick={0,5,...,30},
- xmax=30,
- ymax=35,
- ytick={0,5,...,30},
- scaled ticks=false,
- axis lines=left,
- width=10cm,
- height=7cm,
- legend entries={Python,Ruby,my NFA},
- legend pos=north west,
- legend cell align=left]
-\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
-\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data};
-\addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data};
-\end{axis}
-\end{tikzpicture}
-
-The punchline is that many existing libraries do depth-first search
-in NFAs (backtracking).
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-% \begin{frame}[c]
-% \frametitle{DFA to Rexp}
-
-% \begin{center}
-% \begin{tikzpicture}[scale=2,>=stealth',very thick,
-% every state/.style={minimum size=0pt,
-% draw=blue!50,very thick,fill=blue!20},]
-% \node[state, initial] (q0) at ( 0,1) {$q_0$};
-% \node[state] (q1) at ( 1,1) {$q_1$};
-% \node[state, accepting] (q2) at ( 2,1) {$q_2$};
-% \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
-% (q1) edge[bend left] node[above] {\alert{$b$}} (q0)
-% (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
-% (q1) edge node[above] {\alert{$a$}} (q2)
-% (q2) edge [loop right] node {\alert{$a$}} ()
-% (q0) edge [loop below] node {\alert{$b$}} ();
-% \end{tikzpicture}
-% \end{center}\bigskip
-
-% \begin{center}
-% \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l}
-% \bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b + q_2\,b$} & (start state)\\
-% \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\
-% \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\
-
-% \end{tabular}
-% \end{center}
-
-% Arden's Lemma:
-% \begin{center}
-% If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
-% \end{center}
-
-
-% \end{frame}
-% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-% \begin{frame}[c]
-% \frametitle{DFA Minimisation}
-
-% \begin{enumerate}
-% \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$}
-% \item Mark all pairs that accepting and non-accepting states
-% \item For all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether
-% \begin{center}
-% \bl{$(\delta(q, c), \delta(p,c))$}
-% \end{center}
-% are marked. If yes, then also mark \bl{$(q, p)$}.
-% \item Repeat last step until no change.
-% \item All unmarked pairs can be merged.
-% \end{enumerate}
-
-% \end{frame}
-% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-% \begin{frame}[c]
-
-% \begin{center}
-% \begin{tabular}{@{\hspace{-8mm}}cc@{}}
-% \begin{tikzpicture}[>=stealth',very thick,auto,
-% every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]
-% \node[state,initial] (q_0) {$q_0$};
-% \node[state] (q_1) [right=of q_0] {$q_1$};
-% \node[state] (q_2) [below right=of q_0] {$q_2$};
-% \node[state] (q_3) [right=of q_2] {$q_3$};
-% \node[state, accepting] (q_4) [right=of q_1] {$q_4$};
-% \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1);
-% \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4);
-% \path[->] (q_4) edge [loop right] node {\alert{$a, b$}} ();
-% \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4);
-% \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3);
-% \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2);
-% \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2);
-% \path[->] (q_2) edge [loop left] node {\alert{$b$}} ();
-% \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);
-% \end{tikzpicture}
-% &
-% \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm]
-% \draw (0,0) -- (4,0);
-% \draw (0,1) -- (4,1);
-% \draw (0,2) -- (3,2);
-% \draw (0,3) -- (2,3);
-% \draw (0,4) -- (1,4);
-
-% \draw (0,0) -- (0, 4);
-% \draw (1,0) -- (1, 4);
-% \draw (2,0) -- (2, 3);
-% \draw (3,0) -- (3, 2);
-% \draw (4,0) -- (4, 1);
-
-% \draw (0.5,-0.5) node {$q_0$};
-% \draw (1.5,-0.5) node {$q_1$};
-% \draw (2.5,-0.5) node {$q_2$};
-% \draw (3.5,-0.5) node {$q_3$};
-
-% \draw (-0.5, 3.5) node {$q_1$};
-% \draw (-0.5, 2.5) node {$q_2$};
-% \draw (-0.5, 1.5) node {$q_3$};
-% \draw (-0.5, 0.5) node {$q_4$};
-
-% \draw (0.5,0.5) node {\large$\star$};
-% \draw (1.5,0.5) node {\large$\star$};
-% \draw (2.5,0.5) node {\large$\star$};
-% \draw (3.5,0.5) node {\large$\star$};
-% \draw (0.5,1.5) node {\large$\star$};
-% \draw (2.5,1.5) node {\large$\star$};
-% \draw (0.5,3.5) node {\large$\star$};
-% \draw (1.5,2.5) node {\large$\star$};
-% \end{tikzpicture}}
-% \end{tabular}
-% \end{center}
-
-
-% \mbox{}\\[-20mm]\mbox{}
-
-% \begin{center}
-% \begin{tikzpicture}[>=stealth',very thick,auto,
-% every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]
-% \node[state,initial] (q_02) {$q_{0, 2}$};
-% \node[state] (q_13) [right=of q_02] {$q_{1, 3}$};
-% \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$};
-% \path[->] (q_02) edge [bend left] node [above] {\alert{$a$}} (q_13);
-% \path[->] (q_13) edge [bend left] node [below] {\alert{$b$}} (q_02);
-% \path[->] (q_02) edge [loop below] node {\alert{$b$}} ();
-% \path[->] (q_13) edge node [above] {\alert{$a$}} (q_4);
-% \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} ();
-% \end{tikzpicture}\\
-% minimal automaton
-% \end{center}
-
-% \end{frame}
-% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Regular Languages}
-
-Two equivalent definitions:\bigskip
-
-\begin{quote}\rm A language is \alert{regular} iff there exists a
-regular expression that recognises all its strings.
-\end{quote}
-
-\begin{quote}\rm A language is \alert{regular} iff there exists an
-automaton that recognises all its strings.
-\end{quote}\bigskip\bigskip
-
-
-\small
-for example \bl{$a^nb^n$} is not regular
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Negation}
-
-Regular languages are closed under negation:\bigskip
-
-\begin{center}
-\begin{tikzpicture}[scale=2,>=stealth',very thick,
- every state/.style={minimum size=0pt,
- draw=blue!50,very thick,fill=blue!20}]
- \only<1>{\node[state,initial] (q0) at ( 0,1) {$q_0$};}
- \only<2>{\node[state,initial,accepting] (q0) at ( 0,1) {$q_0$};}
- \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};}
- \only<2>{\node[state,accepting] (q1) at ( 1,1) {$q_1$};}
- \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};}
- \only<2>{\node[state] (q2) at ( 2,1) {$q_2$};}
- \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
- (q1) edge[bend left] node[above] {\alert{$b$}} (q0)
- (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
- (q1) edge node[above] {\alert{$a$}} (q2)
- (q2) edge [loop right] node {\alert{$a$}} ()
- (q0) edge [loop below] node {\alert{$b$}} ();
-\end{tikzpicture}
-\end{center}\bigskip\bigskip
-
-But requires that the automaton is \alert{completed}!
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
@@ -449,7 +117,7 @@
rectangle,rounded corners=3mm,
very thick,draw=black!50,
minimum height=18mm, minimum width=20mm,
- top color=white,bottom color=black!20}]
+ top color=white,bottom color=black!20,drop shadow}]
\node at (3.05, 1.8) {\Large\bf Write a compiler};
@@ -509,7 +177,7 @@
\begin{frame}[c]
\frametitle{Lexing: Test Case}
-\mbox{\lstinputlisting[language=While]{../progs/fib.while}}
+??%\mbox{\lstinputlisting[language=While]{../progs/fib.while}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -1474,6 +1142,416 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Last Week\\[-2mm]
+ Regexes and Values\end{tabular}}
+
+Regular expressions and their corresponding values:
+
+\begin{center}
+\begin{columns}
+\begin{column}{3cm}
+\begin{tabular}{@{}rrl@{}}
+ \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$}\\
+ & \bl{$\mid$} & \bl{$\ONE$} \\
+ & \bl{$\mid$} & \bl{$c$} \\
+ & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\
+ & \bl{$\mid$} & \bl{$r_1 + r_2$} \\
+ \\
+ & \bl{$\mid$} & \bl{$r^*$} \\
+ \end{tabular}
+\end{column}
+\begin{column}{3cm}
+\begin{tabular}{@{\hspace{-7mm}}rrl@{}}
+ \bl{$v$} & \bl{$::=$} & \\
+ & & \bl{$Empty$} \\
+ & \bl{$\mid$} & \bl{$Char(c)$} \\
+ & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\
+ & \bl{$\mid$} & \bl{$Left(v)$} \\
+ & \bl{$\mid$} & \bl{$Right(v)$} \\
+ & \bl{$\mid$} & \bl{$Stars [v_1,\ldots\,v_n]$} \\
+ \end{tabular}
+\end{column}
+\end{columns}
+\end{center}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{textblock}{10}(3,5)
+\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
+\node (r1) {\bl{$r_1$}};
+\node (r2) [right=of r1] {\bl{$r_2$}};
+\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
+\node (r3) [right=of r2] {\bl{$r_3$}};
+\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
+\node (r4) [right=of r3] {\bl{$r_4$}};
+\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
+\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
+\node (v4) [below=of r4] {\bl{$v_4$}};
+\draw[->,line width=1mm] (r4) -- (v4);
+\node (v3) [left=of v4] {\bl{$v_3$}};
+\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
+\node (v2) [left=of v3] {\bl{$v_2$}};
+\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
+\node (v1) [left=of v2] {\bl{$v_1$}};
+\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
+\draw[->,line width=0.5mm] (r3) -- (v3);
+\draw[->,line width=0.5mm] (r2) -- (v2);
+\draw[->,line width=0.5mm] (r1) -- (v1);
+\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
+\end{tikzpicture}
+\end{textblock}
+
+\begin{textblock}{6}(1,0.8)
+\begin{bubble}[6cm]
+\small
+\begin{tabular}{ll}
+\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
+\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\
+\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\
+\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}
+
+\begin{textblock}{6}(1,11.4)
+\begin{bubble}[7.6cm]
+\small
+\begin{tabular}{ll}
+\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\
+\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\
+\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\
+\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}
+
+\begin{textblock}{6}(12,11.4)
+\begin{bubble}[2cm]
+\small
+\begin{tabular}{ll}
+\bl{$|v_1|$}: & \bl{$abc$}\\
+\bl{$|v_2|$}: & \bl{$bc$}\\
+\bl{$|v_3|$}: & \bl{$c$}\\
+\bl{$|v_4|$}: & \bl{$[]$}
+\end{tabular}
+\end{bubble}
+\end{textblock}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Simplification}
+
+\begin{itemize}
+\item If we simplify after the derivative, then we are builing the
+value for the simplified regular expression, but \emph{not} for the original
+regular expression.
+\end{itemize}
+
+\begin{center}
+\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
+\node (r1) {\bl{$r_1$}};
+\node (r2) [right=of r1] {\bl{$r_2$}};
+\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
+\node (r3) [right=of r2] {\bl{$r_3$}};
+\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
+\node (r4) [right=of r3] {\bl{$r_4$}};
+\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
+\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
+\node (v4) [below=of r4] {\bl{$v_4$}};
+\draw[->,line width=1mm] (r4) -- (v4);
+\node (v3) [left=of v4] {\bl{$v_3$}};
+\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
+\node (v2) [left=of v3] {\bl{$v_2$}};
+\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
+\node (v1) [left=of v2] {\bl{$v_1$}};
+\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
+\draw[->,line width=0.5mm] (r3) -- (v3);
+\draw[->,line width=0.5mm] (r2) -- (v2);
+\draw[->,line width=0.5mm] (r1) -- (v1);
+\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
+\end{tikzpicture}
+\end{center}
+
+\small
+\hspace{4.5cm}\bl{$(b \cdot c) + (\ZERO + \ONE)$}
+$\mapsto$
+\bl{$(b \cdot c) + \ONE$}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% \begin{frame}[t]
+
+% \begin{center}
+% \bl{$\only<1>{(b \cdot c)}%
+% \only<2-3>{(\underline{b \cdot c})}%
+% \only<1-3>{+}%
+% \only<1>{(\ZERO + \ONE)}%
+% \only<2-3>{(\underline{\ZERO + \ONE})}$}%
+% \only<4->{%
+% \bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}%
+% }
+% $\mapsto$
+% \bl{$(b \cdot c) + \ONE$}
+% \end{center}\bigskip
+
+% \onslide<3->{%
+% \begin{center}
+% \begin{tabular}{lcl}
+% \bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\
+% \bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$}
+% \end{tabular}
+% \end{center}}
+
+% \only<4>{%
+% \begin{center}
+% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
+% \bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\
+% \quad \bl{$\lambda v.\,$}
+% case \bl{$v = Left(v')$}:
+% & return \bl{$Left(f_{s1}(v'))$}\\
+% \quad \phantom{$\lambda v.\,$}
+% case \bl{$v = Right(v')$}:
+% & return \bl{$Right(f_{s2}(v'))$}\\
+% \end{tabular}
+% \end{center}}%
+% \only<5->{%
+% \begin{center}
+% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
+% \only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\
+% \quad \bl{$\lambda v.\,$}
+% case \bl{$v = Left(v')$}:
+% & return \bl{$Left(v')$}\\
+% \quad \phantom{$\lambda v.\,$}
+% case \bl{$v = Right(v')$}:
+% & return \bl{$Right(Right(v'))$}\\
+% \end{tabular}
+% \end{center}}%
+
+% \only<6->{%
+% \begin{center}
+% \begin{tabular}{@{}l@{\hspace{4mm}}l@{}}
+% \bl{$\textit{mkeps}$} simplified case: &
+% \bl{$\textit{Right}(\textit{Empty})$}\\
+% rectified case: &
+% \bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$}
+% \end{tabular}
+% \end{center}}%
+
+% \end{frame}
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Records}
+
+\begin{itemize}
+\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause
+
+\item \bl{$nullable(x:r) \dn nullable(r)$}
+\item \bl{$der\,c\,(x:r) \dn der\,c\,r$}
+\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$}
+\item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$}
+\end{itemize}\bigskip\bigskip\pause
+
+\small
+for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Environments}
+
+Obtaining the ``recorded'' parts of a value:
+
+\begin{center}
+\begin{tabular}{lcl}
+ \bl{$env(Empty)$} & \bl{$\dn$} & \bl{$[]$}\\
+ \bl{$env(Char(c))$} & \bl{$\dn$} & \bl{$[]$}\\
+ \bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
+ \bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
+ \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\
+ \bl{$env(Stars [v_1,\ldots ,v_n])$} & \bl{$\dn$} &
+ \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\
+ \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{While Tokens}
+
+\begin{center}
+\begin{tabular}{@{}r@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}
+\pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\
+ & & \phantom{(}\pcode{("i" : ID)} +\\
+ & & \phantom{(}\pcode{("o" : OP)} + \\
+ & & \phantom{(}\pcode{("n" : NUM)} + \\
+ & & \phantom{(}\pcode{("s" : SEMI)} +\\
+ & & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\
+ & & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\
+ & & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$}
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+
+\consolas
+\begin{center}
+\code{"if true then then 42 else +"}
+\end{center}
+
+\only<1>{
+\small\begin{tabular}{l}
+KEYWORD(if),\\
+WHITESPACE,\\
+IDENT(true),\\
+WHITESPACE,\\
+KEYWORD(then),\\
+WHITESPACE,\\
+KEYWORD(then),\\
+WHITESPACE,\\
+NUM(42),\\
+WHITESPACE,\\
+KEYWORD(else),\\
+WHITESPACE,\\
+OP(+)
+\end{tabular}}
+
+\only<2>{
+\small\begin{tabular}{l}
+KEYWORD(if),\\
+IDENT(true),\\
+KEYWORD(then),\\
+KEYWORD(then),\\
+NUM(42),\\
+KEYWORD(else),\\
+OP(+)
+\end{tabular}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%\begin{frame}[c]
+%\frametitle{Coursework: PLs (16)}
+%
+%\begin{itemize}
+%\item Java (16)
+%\item C++, C, C\# (14)
+%\item JavaScript (10)
+%\item Scala (9)
+%\item Python (9)
+%\item PHP (6)
+%\item Haskell (3)
+%\item Ruby (4)
+%\item Bash, Perl, Powershell (2)
+%\item TypeScript (1)
+%\item R (1)
+%\item Coconut (1)
+%\item Pascal (1)
+%\end{itemize}
+%
+%\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%\begin{frame}[c]
+%\frametitle{Coursework: Nullable}
+%
+%\begin{center}
+%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+% \bl{$nullable([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\
+% \bl{$nullable(r^+)$} & \bl{$\dn$} & $?$\\
+% \bl{$nullable(r^?)$} & \bl{$\dn$} & $?$\\
+% \bl{$nullable(r^{\{n\}})$} & \bl{$\dn$} & $?$\\
+% \bl{$nullable(r^{\{n..\}})$} & \bl{$\dn$} & $?$\\
+% \bl{$nullable(r^{\{..n\}})$} & \bl{$\dn$} & $?$\\
+% \bl{$nullable(r^{\{n..m\}})$} & \bl{$\dn$} & $?$\\
+% \bl{$nullable(\sim{}r)$} & \bl{$\dn$} & $?$\\
+%
+%\end{tabular}
+%\end{center}
+%
+%\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%\begin{frame}[c]
+%%%\frametitle{Coursework: der}
+%
+%\begin{center}
+%\begin{tabular}{@ {}l@ {\hspace{1mm}}c@ {\hspace{1mm}}l@ {}}
+% \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\
+% \bl{$der\, c\, (r^+)$} & \bl{$\dn$} & $?$\\
+% \bl{$der\, c\, (r^?)$} & \bl{$\dn$} & $?$\\
+% \bl{$der\, c\, (r^{\{n\}})$} & \bl{$\dn$} &
+% \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-\liningnums{1}\}}$}\\
+% \bl{$der\, c\, (r^{\{n..\}})$} & \bl{$\dn$} &
+% \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\
+% & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..\}}$}\\
+% \bl{$der\, c\, (r^{\{..n\}})$} & \bl{$\dn$} &
+% \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-\liningnums{1}\}}$}\\
+%
+% \bl{$der\, c\, (r^{\{n..m\}})$} & \bl{$\dn$} &
+% \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\
+% \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-\liningnums{1}\}}$}}\\
+% \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else
+% \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..m-\liningnums{1}\}}$}}\\
+% \bl{$der\, c\, (\sim{}r)$} & \bl{$\dn$} & $?$\\
+%\end{tabular}
+%\end{center}
+%
+%\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%\begin{frame}[c]
+%\frametitle{Coursework: CFUN}
+%
+%\begin{center}
+%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+% \bl{$nullable(CFUN(\_))$} & \bl{$\dn$} & \bl{$false$}\\
+% \bl{$der\,c\,(CFUN(f))$} & \bl{$\dn$} &
+% \bl{$if\;f(c)\;then\;\ONE\;else\;\ZERO$}\bigskip\\
+% \bl{$CHAR(c)$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;c=d)$}\\
+% \bl{$CSET([c_1,\ldots,c_n])$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;d\in [c_1,\ldots,c_n])$}\\
+% \bl{$ALL$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;true)$}\\
+%\end{tabular}
+%\end{center}
+%
+%\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
\end{document}
%%% Local Variables:
Binary file slides/slides05.pdf has changed
--- a/slides/slides05.tex Thu Jul 30 13:50:54 2020 +0100
+++ b/slides/slides05.tex Sat Aug 15 14:18:37 2020 +0100
@@ -1,6 +1,6 @@
% !TEX program = xelatex
-\documentclass[dvipsnames,14pt,t]{beamer}
+\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
\usepackage{../slides}
\usepackage{../graphics}
\usepackage{../langs}
@@ -25,448 +25,55 @@
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Compilers and \\[-2mm]
- \LARGE Formal Languages (5)\\[3mm]
+ \LARGE Formal Languages\\[3mm]
\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)\\
+ %Office Hours: & Thursdays 12 -- 14\\
+ %Location: & N7.07 (North Wing, Bush House)\\
Slides \& Progs: & KEATS (also homework is there)\\
\end{tabular}
+\end{center}
+
+ \begin{center}
+ \begin{tikzpicture}
+ \node[drop shadow,fill=white,inner sep=0pt]
+ {\footnotesize\rowcolors{1}{capri!10}{white}
+ \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
+ 1 Introduction, Languages & 6 While-Language \\
+ 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
+ 3 Automata, Regular Languages & 8 Compiling Functional Languages \\
+ 4 Lexing, Tokenising & 9 Optimisations \\
+ \cellcolor{blue!50}
+ 5 Grammars, Parsing & 10 LLVM \\ \hline
+ \end{tabular}%
+ };
+ \end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
- \frametitle{Coursework 1: Submissions}
-
- \begin{itemize}
- \item Scala (29)
- \item Haskell (1)
- \item Kotlin (1)
- \item Rust (1)
- \end{itemize}\bigskip\bigskip
-
- \small
- Please get in contact if you intend to do CW Strand 2. No zips please.
- Give definitions also on paper if asked. BTW, simp
- can stay unchanged. Use \texttt{ders} for CW2, not \texttt{ders2}!
- \end{frame}
- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Last Week\\[-2mm]
- Regexes and Values\end{tabular}}
-
-Regular expressions and their corresponding values:
-
-\begin{center}
-\begin{columns}
-\begin{column}{3cm}
-\begin{tabular}{@{}rrl@{}}
- \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$}\\
- & \bl{$\mid$} & \bl{$\ONE$} \\
- & \bl{$\mid$} & \bl{$c$} \\
- & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\
- & \bl{$\mid$} & \bl{$r_1 + r_2$} \\
- \\
- & \bl{$\mid$} & \bl{$r^*$} \\
- \end{tabular}
-\end{column}
-\begin{column}{3cm}
-\begin{tabular}{@{\hspace{-7mm}}rrl@{}}
- \bl{$v$} & \bl{$::=$} & \\
- & & \bl{$Empty$} \\
- & \bl{$\mid$} & \bl{$Char(c)$} \\
- & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\
- & \bl{$\mid$} & \bl{$Left(v)$} \\
- & \bl{$\mid$} & \bl{$Right(v)$} \\
- & \bl{$\mid$} & \bl{$Stars [v_1,\ldots\,v_n]$} \\
- \end{tabular}
-\end{column}
-\end{columns}
-\end{center}
-
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-
-\begin{textblock}{10}(3,5)
-\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
-\node (r1) {\bl{$r_1$}};
-\node (r2) [right=of r1] {\bl{$r_2$}};
-\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
-\node (r3) [right=of r2] {\bl{$r_3$}};
-\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
-\node (r4) [right=of r3] {\bl{$r_4$}};
-\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
-\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
-\node (v4) [below=of r4] {\bl{$v_4$}};
-\draw[->,line width=1mm] (r4) -- (v4);
-\node (v3) [left=of v4] {\bl{$v_3$}};
-\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
-\node (v2) [left=of v3] {\bl{$v_2$}};
-\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
-\node (v1) [left=of v2] {\bl{$v_1$}};
-\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
-\draw[->,line width=0.5mm] (r3) -- (v3);
-\draw[->,line width=0.5mm] (r2) -- (v2);
-\draw[->,line width=0.5mm] (r1) -- (v1);
-\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
-\end{tikzpicture}
-\end{textblock}
-
-\begin{textblock}{6}(1,0.8)
-\begin{bubble}[6cm]
-\small
-\begin{tabular}{ll}
-\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
-\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\
-\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\
-\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\
-\end{tabular}
-\end{bubble}
-\end{textblock}
-
-\begin{textblock}{6}(1,11.4)
-\begin{bubble}[7.6cm]
-\small
-\begin{tabular}{ll}
-\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\
-\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\
-\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\
-\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\
-\end{tabular}
-\end{bubble}
-\end{textblock}
-
-\begin{textblock}{6}(12,11.4)
-\begin{bubble}[2cm]
-\small
-\begin{tabular}{ll}
-\bl{$|v_1|$}: & \bl{$abc$}\\
-\bl{$|v_2|$}: & \bl{$bc$}\\
-\bl{$|v_3|$}: & \bl{$c$}\\
-\bl{$|v_4|$}: & \bl{$[]$}
-\end{tabular}
-\end{bubble}
-\end{textblock}
-
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
+%\begin{frame}[c]
+% \frametitle{Coursework 1: Submissions}
+%
+% \begin{itemize}
+% \item Scala (29)
+% \item Haskell (1)
+% \item Kotlin (1)
+% \item Rust (1)
+% \end{itemize}\bigskip\bigskip
+%
+% \small
+% Please get in contact if you intend to do CW Strand 2. No zips please.
+% Give definitions also on paper if asked. BTW, simp
+% can stay unchanged. Use \texttt{ders} for CW2, not \texttt{ders2}!
+% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Simplification}
-
-\begin{itemize}
-\item If we simplify after the derivative, then we are builing the
-value for the simplified regular expression, but \emph{not} for the original
-regular expression.
-\end{itemize}
-
-\begin{center}
-\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
-\node (r1) {\bl{$r_1$}};
-\node (r2) [right=of r1] {\bl{$r_2$}};
-\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
-\node (r3) [right=of r2] {\bl{$r_3$}};
-\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
-\node (r4) [right=of r3] {\bl{$r_4$}};
-\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
-\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
-\node (v4) [below=of r4] {\bl{$v_4$}};
-\draw[->,line width=1mm] (r4) -- (v4);
-\node (v3) [left=of v4] {\bl{$v_3$}};
-\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
-\node (v2) [left=of v3] {\bl{$v_2$}};
-\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
-\node (v1) [left=of v2] {\bl{$v_1$}};
-\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
-\draw[->,line width=0.5mm] (r3) -- (v3);
-\draw[->,line width=0.5mm] (r2) -- (v2);
-\draw[->,line width=0.5mm] (r1) -- (v1);
-\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
-\end{tikzpicture}
-\end{center}
-
-\small
-\hspace{4.5cm}\bl{$(b \cdot c) + (\ZERO + \ONE)$}
-$\mapsto$
-\bl{$(b \cdot c) + \ONE$}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-% \begin{frame}[t]
-
-% \begin{center}
-% \bl{$\only<1>{(b \cdot c)}%
-% \only<2-3>{(\underline{b \cdot c})}%
-% \only<1-3>{+}%
-% \only<1>{(\ZERO + \ONE)}%
-% \only<2-3>{(\underline{\ZERO + \ONE})}$}%
-% \only<4->{%
-% \bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}%
-% }
-% $\mapsto$
-% \bl{$(b \cdot c) + \ONE$}
-% \end{center}\bigskip
-
-% \onslide<3->{%
-% \begin{center}
-% \begin{tabular}{lcl}
-% \bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\
-% \bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$}
-% \end{tabular}
-% \end{center}}
-
-% \only<4>{%
-% \begin{center}
-% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
-% \bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\
-% \quad \bl{$\lambda v.\,$}
-% case \bl{$v = Left(v')$}:
-% & return \bl{$Left(f_{s1}(v'))$}\\
-% \quad \phantom{$\lambda v.\,$}
-% case \bl{$v = Right(v')$}:
-% & return \bl{$Right(f_{s2}(v'))$}\\
-% \end{tabular}
-% \end{center}}%
-% \only<5->{%
-% \begin{center}
-% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
-% \only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\
-% \quad \bl{$\lambda v.\,$}
-% case \bl{$v = Left(v')$}:
-% & return \bl{$Left(v')$}\\
-% \quad \phantom{$\lambda v.\,$}
-% case \bl{$v = Right(v')$}:
-% & return \bl{$Right(Right(v'))$}\\
-% \end{tabular}
-% \end{center}}%
-
-% \only<6->{%
-% \begin{center}
-% \begin{tabular}{@{}l@{\hspace{4mm}}l@{}}
-% \bl{$\textit{mkeps}$} simplified case: &
-% \bl{$\textit{Right}(\textit{Empty})$}\\
-% rectified case: &
-% \bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$}
-% \end{tabular}
-% \end{center}}%
-
-% \end{frame}
-% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Records}
-
-\begin{itemize}
-\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause
-
-\item \bl{$nullable(x:r) \dn nullable(r)$}
-\item \bl{$der\,c\,(x:r) \dn der\,c\,r$}
-\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$}
-\item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$}
-\end{itemize}\bigskip\bigskip\pause
-
-\small
-for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Environments}
-
-Obtaining the ``recorded'' parts of a value:
-
-\begin{center}
-\begin{tabular}{lcl}
- \bl{$env(Empty)$} & \bl{$\dn$} & \bl{$[]$}\\
- \bl{$env(Char(c))$} & \bl{$\dn$} & \bl{$[]$}\\
- \bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
- \bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
- \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\
- \bl{$env(Stars [v_1,\ldots ,v_n])$} & \bl{$\dn$} &
- \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\
- \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{While Tokens}
-
-\begin{center}
-\begin{tabular}{@{}r@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}
-\pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\
- & & \phantom{(}\pcode{("i" : ID)} +\\
- & & \phantom{(}\pcode{("o" : OP)} + \\
- & & \phantom{(}\pcode{("n" : NUM)} + \\
- & & \phantom{(}\pcode{("s" : SEMI)} +\\
- & & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\
- & & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\
- & & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$}
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-
-\consolas
-\begin{center}
-\code{"if true then then 42 else +"}
-\end{center}
-
-\only<1>{
-\small\begin{tabular}{l}
-KEYWORD(if),\\
-WHITESPACE,\\
-IDENT(true),\\
-WHITESPACE,\\
-KEYWORD(then),\\
-WHITESPACE,\\
-KEYWORD(then),\\
-WHITESPACE,\\
-NUM(42),\\
-WHITESPACE,\\
-KEYWORD(else),\\
-WHITESPACE,\\
-OP(+)
-\end{tabular}}
-
-\only<2>{
-\small\begin{tabular}{l}
-KEYWORD(if),\\
-IDENT(true),\\
-KEYWORD(then),\\
-KEYWORD(then),\\
-NUM(42),\\
-KEYWORD(else),\\
-OP(+)
-\end{tabular}}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%\begin{frame}[c]
-%\frametitle{Coursework: PLs (16)}
-%
-%\begin{itemize}
-%\item Java (16)
-%\item C++, C, C\# (14)
-%\item JavaScript (10)
-%\item Scala (9)
-%\item Python (9)
-%\item PHP (6)
-%\item Haskell (3)
-%\item Ruby (4)
-%\item Bash, Perl, Powershell (2)
-%\item TypeScript (1)
-%\item R (1)
-%\item Coconut (1)
-%\item Pascal (1)
-%\end{itemize}
-%
-%\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%\begin{frame}[c]
-%\frametitle{Coursework: Nullable}
-%
-%\begin{center}
-%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
-% \bl{$nullable([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\
-% \bl{$nullable(r^+)$} & \bl{$\dn$} & $?$\\
-% \bl{$nullable(r^?)$} & \bl{$\dn$} & $?$\\
-% \bl{$nullable(r^{\{n\}})$} & \bl{$\dn$} & $?$\\
-% \bl{$nullable(r^{\{n..\}})$} & \bl{$\dn$} & $?$\\
-% \bl{$nullable(r^{\{..n\}})$} & \bl{$\dn$} & $?$\\
-% \bl{$nullable(r^{\{n..m\}})$} & \bl{$\dn$} & $?$\\
-% \bl{$nullable(\sim{}r)$} & \bl{$\dn$} & $?$\\
-%
-%\end{tabular}
-%\end{center}
-%
-%\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%\begin{frame}[c]
-%%%\frametitle{Coursework: der}
-%
-%\begin{center}
-%\begin{tabular}{@ {}l@ {\hspace{1mm}}c@ {\hspace{1mm}}l@ {}}
-% \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\
-% \bl{$der\, c\, (r^+)$} & \bl{$\dn$} & $?$\\
-% \bl{$der\, c\, (r^?)$} & \bl{$\dn$} & $?$\\
-% \bl{$der\, c\, (r^{\{n\}})$} & \bl{$\dn$} &
-% \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-\liningnums{1}\}}$}\\
-% \bl{$der\, c\, (r^{\{n..\}})$} & \bl{$\dn$} &
-% \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\
-% & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..\}}$}\\
-% \bl{$der\, c\, (r^{\{..n\}})$} & \bl{$\dn$} &
-% \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-\liningnums{1}\}}$}\\
-%
-% \bl{$der\, c\, (r^{\{n..m\}})$} & \bl{$\dn$} &
-% \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\
-% \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-\liningnums{1}\}}$}}\\
-% \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else
-% \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..m-\liningnums{1}\}}$}}\\
-% \bl{$der\, c\, (\sim{}r)$} & \bl{$\dn$} & $?$\\
-%\end{tabular}
-%\end{center}
-%
-%\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%\begin{frame}[c]
-%\frametitle{Coursework: CFUN}
-%
-%\begin{center}
-%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
-% \bl{$nullable(CFUN(\_))$} & \bl{$\dn$} & \bl{$false$}\\
-% \bl{$der\,c\,(CFUN(f))$} & \bl{$\dn$} &
-% \bl{$if\;f(c)\;then\;\ONE\;else\;\ZERO$}\bigskip\\
-% \bl{$CHAR(c)$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;c=d)$}\\
-% \bl{$CSET([c_1,\ldots,c_n])$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;d\in [c_1,\ldots,c_n])$}\\
-% \bl{$ALL$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;true)$}\\
-%\end{tabular}
-%\end{center}
-%
-%\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Lexer, Parser}
@@ -478,7 +85,7 @@
rectangle,rounded corners=3mm,
very thick,draw=black!50,
minimum height=18mm, minimum width=20mm,
- top color=white,bottom color=black!20}]
+ top color=white,bottom color=black!20,drop shadow}]
\node (0) at (-2.3,0) {};
\node (A) at (0,0) [node] {};
@@ -1239,8 +846,8 @@
\mbox{}\\[-18mm]\mbox{}
-{\lstset{language=While}%%\fontsize{10}{12}\selectfont
-\texttt{\lstinputlisting{../progs/loops.while}}}
+??%{\lstset{language=While}%%\fontsize{10}{12}\selectfont
+%\texttt{\lstinputlisting{../progs/loops.while}}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
--- a/style.sty Thu Jul 30 13:50:54 2020 +0100
+++ b/style.sty Sat Aug 15 14:18:37 2020 +0100
@@ -9,6 +9,8 @@
\definecolor{darkblue}{rgb}{0,0,0.6}
\usepackage[colorlinks=true,urlcolor=darkblue,linkcolor=darkblue]{hyperref}
\usepackage{soul}
+\usepackage{marginnote}
+\usepackage{fontawesome5}
%%% for regular expressions and values
\newcommand{\ZERO}{\mbox{\bf 0}}
@@ -49,6 +51,12 @@
\def\VS{\Vspace[0.6em]}
+%%% url pointers
+\newcommand{\here}[1]{\marginnote{\href{#1}{\faHandPointRight[regular]}}}
+\newcommand{\video}[1]{\marginnote{\href{#1}{\faFilm}}}
+\newcommand{\alert}{\reversemarginpar\marginpar{\mbox{}\hfill\textcolor{red}{\faExclamationTriangle}}}
+
+
\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}
\newcommand{\defn}[1]{\textit{\textbf{#1}}}
\newcommand{\dq}[1]{\mbox{\tt{"}}#1\mbox{\tt{"}}}
@@ -60,7 +68,7 @@
\makeatother
\newcommand{\HEADER}{{\bf Please submit your solutions via email. Please submit
-only ASCII text or PDFs. Every solution should be preceeded by the corresponding
+only PDFs! Every solution should be preceeded by the corresponding
question text, like:
\begin{center}
@@ -82,7 +90,10 @@
parts in this lecture? Any problems with my Scala code? Please
feel free to share any other questions or concerns. Also, all my
material is \st{crap} imperfect. If you have any suggestions for
-improvement, I am very grateful to hear.}
+improvement, I am very grateful to hear.\medskip
+
+If *you* want to share anything (code, videos, links), you are
+encouraged to do so. Just drop me an email.}
% CW deadlines