--- a/slides/slides04.tex Fri Oct 09 14:48:06 2015 +0100
+++ b/slides/slides04.tex Fri Oct 16 08:42:21 2015 +0100
@@ -49,7 +49,9 @@
\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] (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}
@@ -58,9 +60,8 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[t]
-\frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}}
+\frametitle{\bl{$a^?^{\{n\}} \cdot a^{\{n\}}$}}
\begin{tikzpicture}
\begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs},
@@ -85,10 +86,9 @@
\end{axis}
\end{tikzpicture}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{DFA to Rexp}
@@ -118,18 +118,16 @@
\end{tabular}
\end{center}
-\onslide<2->{
Arden's Lemma:
\begin{center}
If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
\end{center}
-}
+
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
\frametitle{DFA Minimisation}
@@ -145,65 +143,6 @@
\item All unmarked pairs can be merged.
\end{enumerate}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-
-\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_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}
-\end{center}
-
-\mbox{}\\[-20mm]\mbox{}
-
-\begin{center}
-\begin{tikzpicture}[scale=0.8,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$};
-\end{tikzpicture}
-\end{center}
-
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -288,56 +227,6 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{Alternatives}
-\mbox{}\\[-17mm]\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}]
-\only<1>{\node[state,initial] (q_0) {$q_0$};}
-\only<2->{\node[state,accepting] (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$};
-\only<1>{\node[state, accepting] (q_4) [right=of q_1] {$q_4$};}
-\only<2->{\node[state, initial right] (q_4) [right=of q_1] {$q_4$};}
-\only<1-2>{
-\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 above] 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);}
-\only<3->{
-\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 above] 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}
-\end{center}
-\mbox{}\\[-18mm]
-
-\begin{itemize}
-\item<2-> exchange initial / accepting states
-\item<3-> reverse all edges
-\item<4-> subset construction $\Rightarrow$ DFA
-\item<5-> repeat once more \onslide<6->{$\Rightarrow$ minimal DFA}
-\end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
\frametitle{Regular Languages}
Two equivalent definitions:\bigskip
@@ -382,13 +271,77 @@
\end{tikzpicture}
\end{center}\bigskip\bigskip
-\onslide<2>{But requires that the automaton is \alert{completed}!}
+But requires that the automaton is \alert{completed}!
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
+\frametitle{The Goal of this Course}
+\mbox{}\\[-26mm]\mbox{}
+
+\begin{center}
+ \begin{tikzpicture}[scale=1,
+ node/.style={
+ rectangle,rounded corners=3mm,
+ very thick,draw=black!50,
+ minimum height=18mm, minimum width=20mm,
+ top color=white,bottom color=black!20}]
+
+ \node at (3.05, 1.8) {\Large\bf Write A Compiler};
+
+ \node (0) at (-2.3,0) {};
+
+ \node (A) at (0,0) [node] {};
+ \node [below right] at (A.north west) {lexer};
+
+ \node (B) at (3,0) [node] {};
+ \node [below right=1mm] at (B.north west)
+ {\mbox{}\hspace{-1mm}parser};
+
+ \node (C) at (6,0) [node] {};
+ \node [below right] at (C.north west)
+ {\mbox{}\hspace{-1mm}code gen};
+
+ \node (1) at (8.4,0) {};
+
+ \draw [->,line width=4mm] (0) -- (A);
+ \draw [->,line width=4mm] (A) -- (B);
+ \draw [->,line width=4mm] (B) -- (C);
+ \draw [->,line width=4mm] (C) -- (1);
+ \end{tikzpicture}
+ \end{center}
+
+Today a lexer.
+
+\end{frame}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Survey: Thanks!}
+\small
+
+\begin{itemize}
+\item {\bf My Voice} ``lecturer speaks in a low voice and
+ is hard to hear him'' ``please use mic'' ``please use mic
+ \& lecture recording''
+\item {\bf Pace} ``faster pace'' ``a bit quick for me
+personally''
+\item {\bf Recording} ``please use recording class''
+\item {\bf Module Name} ``misleading''
+\item {\bf Examples} ``more examples''
+\item {\bf Assessment} ``really appreciate extension of
+ first coursework''
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Lexing}
\mbox{\lstinputlisting[language=While]{../progs/fib.while}}
@@ -405,29 +358,6 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{A Compiler}
-
-\begin{tikzpicture}[scale=1]
- \draw[line width=1mm] (-0.3, 0) rectangle (1.5,2);
- \draw[line width=1mm] (-1.8, 0) rectangle (-3.6,2);
- \draw (4.4,1) node {Code Gen};
- \draw (0.6,1.7) node {\small Parser};
- \draw (-2.7,1.7) node {\small Lexer};
-
- \draw[red,->,line width = 2mm] (1.7,1) -- (3.2,1);
- \draw[red,<-,line width = 2mm] (-0.6,1) -- (-1.6,1);
- \draw[red,<-,line width = 2mm] (-3.8,1) -- (-4.8,1);
-
- \draw (-4.6,1.7) node {\small string};
- \draw (-1.1,1.7) node {\small tokens};
- \draw ( 2.3,1.7) node {\small AST};
-\end{tikzpicture}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\tt
@@ -518,6 +448,19 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+The same problem with\medskip
+
+\[
+\bl{(ab + a) \cdot (c + bc)}
+\]\bigskip
+
+and the string $\bl{abc}$
+
+\end{frame}
+
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{POSIX: Two Rules}
@@ -616,6 +559,17 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\small
+
+{\small\lstinputlisting[language=Scala,numbers=none,
+xleftmargin=-5mm] {../progs/app01.scala}}
+
+{\small\lstinputlisting[language=Scala,numbers=none,
+xleftmargin=-5mm] {../progs/app02.scala}}
+
+\end{frame}
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Mkeps}
@@ -659,6 +613,153 @@
\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}
+
+\only<2->{
+\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{$\epsilon \cdot (b \cdot c)$}\\
+\bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\
+\bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<2->{
+\begin{textblock}{6}(5,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}}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Flatten}
+
+Obtaining the string underlying a value:
+
+\begin{center}
+\begin{tabular}{lcl}
+ \bl{$|Empty|$} & \bl{$\dn$} & \bl{$[]$}\\
+ \bl{$|Char(c)|$} & \bl{$\dn$} & \bl{$[c]$}\\
+ \bl{$|Left(v)|$} & \bl{$\dn$} & \bl{$|v|$}\\
+ \bl{$|Right(v)|$} & \bl{$\dn$} & \bl{$|v|$}\\
+ \bl{$|Seq(v_1,v_2)|$}& \bl{$\dn$} & \bl{$|v_1| \,@\, |v_2|$}\\
+ \bl{$|[v_1,\ldots ,v_n]|$} & \bl{$\dn$} & \bl{$|v_1| \,@\ldots @\, |v_n|$}\\
+\end{tabular}
+\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{$\epsilon \cdot (b \cdot c)$}\\
+\bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\
+\bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\
+\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{Lexing}
@@ -719,6 +820,57 @@
\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 (x: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]
+
+\begin{itemize}
+\item Regular expression for email addresses
+
+\begin{center}
+\begin{tabular}{l}
+(name: \bl{$[a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+$})\bl{$\cdot @\cdot$}\\
+\qquad(domain: \bl{$[a\mbox{-}z0\mbox{-}9\,.-]^+$}) \bl{$\cdot .\cdot$}\\
+\qquad\qquad(top\_level: \bl{$[a\mbox{-}z\,.]^{\{2,6\}}$})
+\end{tabular}
+\end{center}
+
+\bl{\[
+\texttt{christian.urban@kcl.ac.uk}
+\]}
+
+\item result environment:
+
+\begin{center}
+\begin{tabular}{l}
+\bl{$[(name:\texttt{christian.urban}),$}\\
+\bl{$\phantom{[}(domain:\texttt{kcl}),$}\\
+\bl{$\phantom{[}(top\_level:\texttt{ac.uk})]$}
+\end{tabular}
+\end{center}
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
@@ -740,6 +892,8 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Simplification}
@@ -775,6 +929,11 @@
\end{tikzpicture}
\end{center}
+\small
+\hspace{4.5cm}\bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}
+$\mapsto$
+\bl{$\epsilon$}
+
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -803,6 +962,94 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Rectification}
+
+\begin{center}
+\begin{tabular}{l}
+\bl{$simp(r)$}:\\
+\quad case \bl{$r = r_1 + r_2$}\\
+\qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\
+\qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\
+\qquad case \bl{$r_{1s} = \varnothing$}:
+ return \bl{$(r_{2s}, \lambda v. \,Right(f_{2s}(v)))$}\\
+\qquad case \bl{$r_{2s} = \varnothing$}:
+ return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\
+\qquad case \bl{$r_{1s} = r_{2s}$}:
+ return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\
+\qquad otherwise:
+ return \bl{$(r_{1s} + r_{2s}, f_{alt}(f_{1s}, f_{2s}))$}\\
+\end{tabular}
+\end{center}
+
+\small
+\begin{center}
+\begin{tabular}{l@{\hspace{1mm}}l}
+\bl{$f_{alt}(f_1, f_2) \dn$}\\
+\qquad \bl{$\lambda v.\,$} case \bl{$v = Left(v')$}:
+ & return \bl{$Left(f_1(v'))$}\\
+\qquad \phantom{$\lambda v.\,$} case \bl{$v = Right(v')$}:
+ & return \bl{$Right(f_2(v'))$}\\
+\end{tabular}
+\end{center}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\begin{frame}[c]
+
+{\footnotesize\lstinputlisting[language=Scala,numbers=none,
+xleftmargin=-5mm] {../progs/app05.scala}}
+
+\end{frame}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Rectification}
+
+\begin{center}
+\begin{tabular}{@{\hspace{-3mm}}l}
+\bl{$simp(r)$}:\ldots\\
+\quad case \bl{$r = r_1 \cdot r_2$}\\
+\qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\
+\qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\
+\qquad case \bl{$r_{1s} = \varnothing$}:
+ return \bl{$(\varnothing, f_{error})$}\\
+\qquad case \bl{$r_{2s} = \varnothing$}:
+ return \bl{$(\varnothing, f_{error})$}\\
+\qquad case \bl{$r_{1s} = \epsilon$}:
+return \bl{$(r_{2s}, \lambda v. \,Seq(f_{1s}(Empty), f_{2s}(v)))$}\\
+\qquad case \bl{$r_{2s} = \epsilon$}:
+return \bl{$(r_{1s}, \lambda v. \,Seq(f_{1s}(v), f_{2s}(Empty)))$}\\
+\qquad otherwise:
+ return \bl{$(r_{1s} \cdot r_{2s}, f_{seq}(f_{1s}, f_{2s}))$}\\
+\end{tabular}
+\end{center}
+
+\small
+\begin{center}
+\begin{tabular}{l@{\hspace{1mm}}l}
+\bl{$f_{seq}(f_1, f_2) \dn$}\\
+\qquad \bl{$\lambda v.\,$ case $v = Seq(v_1, v_2)$}:
+ & return \bl{$Seq(f_1(v_1), f_2(v_2))$}\\
+\end{tabular}
+\end{center}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+\begin{frame}[c]
+
+{\footnotesize\lstinputlisting[language=Scala,numbers=none,
+xleftmargin=-5mm] {../progs/app06.scala}}
+
+\end{frame}
+
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Lexing with Simplification}
@@ -844,6 +1091,29 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+$zeroable(\varnothing)$ & $\dn$ & $true$\\
+$zeroable(\epsilon)$ & $\dn$ & $f\!alse$\\
+$zeroable (c)$ & $\dn$ & $f\!alse$\\
+$zeroable (r_1 + r_2)$ & $\dn$ & $zeroable(r_1) \wedge zeroable(r_2)$ \\
+$zeroable (r_1 \cdot r_2)$ & $\dn$ & $zeroable(r_1) \vee zeroable(r_2)$ \\
+$zeroable (r^*)$ & $\dn$ & $f\!alse$\\
+\end{tabular}
+\end{center}
+
+\begin{center}
+$zeroable(r)$ if and only if $L(r) = \varnothing$
+\end{center}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
\end{document}
%%% Local Variables: