--- a/slides/slides05.tex Sat Oct 18 02:08:17 2014 +0100
+++ b/slides/slides05.tex Mon Oct 20 00:10:57 2014 +0100
@@ -34,83 +34,161 @@
\end{tabular}
\end{center}
\end{frame}
- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{DFA Minimisation}
+\frametitle{\begin{tabular}{c}Last Week\\ Regexes and Values\end{tabular}}
-\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$} tests wether
+Regular expressions and their corresponding values:
+
\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}
+\begin{columns}
+\begin{column}{3cm}
+\begin{tabular}{@{}rrl@{}}
+ \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$}\\
+ & \bl{$\mid$} & \bl{$\epsilon$} \\
+ & \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{$[v_1,\ldots\,v_n]$} \\
+ \end{tabular}
+\end{column}
+\end{columns}
+\end{center}
-\end{frame}}
+
+\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);
+\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{center}
+\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}}
-\mbox{}\\[-20mm]\mbox{}
+\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{Mkeps}
+
+Finding a (posix) value for recognising the empty string:
\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);
+\begin{tabular}{lcl}
+ \bl{$mkeps\,\epsilon$} & \bl{$\dn$} & \bl{$Empty$}\\
+ \bl{$mkeps\,r_1 + r_2$} & \bl{$\dn$} & \bl{if $nullable(r_1)$} \\
+ & & \bl{then $Left(mkeps(r_1))$}\\
+ & & \bl{else $Right(mkeps(r_2))$}\\
+ \bl{$mkeps\,r_1 \cdot r_2$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\
+ \bl{$mkeps\,r^*$} & \bl{$\dn$} & \bl{$[]$} \\
+\end{tabular}
+\end{center}
-\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);
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Inject}
+
+Injecting (``Adding'') a character to a value\\
-\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$};
+\begin{center}
+\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
+ \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$} & \bl{$Char\,c$}\\
+ \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\
+ \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\
+ \bl{$inj\,(r_1 \cdot r_2)\,c\,Seq(v_1,v_2)$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
+ \bl{$inj\,(r_1 \cdot r_2)\,c\,Left(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
+ \bl{$inj\,(r_1 \cdot r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
+ \bl{$inj\,(r^*)\,c\,Seq(v,vs)$} & \bl{$\dn$} & \bl{$inj\,r\,c\,v\,::\,vs$}\\
+\end{tabular}
+\end{center}\bigskip
-\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}\\
+\footnotesize
+\bl{$inj$}: 1st arg $\mapsto$ a rexp; 2nd arg $\mapsto$ a character; 3rd arg $\mapsto$ a value
+\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}
@@ -119,225 +197,263 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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);
+\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}
-&
-\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);
+\end{textblock}
-\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}}
+\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{center}
-
-
-\mbox{}\\[-20mm]\mbox{}
+\end{bubble}
+\end{textblock}
-\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}
+\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}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
+\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}[>=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);}
+\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}
-\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}
+\small
+\hspace{4.5cm}\bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}
+$\mapsto$
+\bl{$\epsilon$}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Rectification}
-\end{itemize}
+\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}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mbox{\lstinputlisting[language=while]{../progs/fib.while}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Lexing with Simplification}
+
+\begin{center}
+\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
+ \bl{$lex\,r\,[]$} & \bl{$\dn$} & \bl{if $nullable(r)$ then $mkeps(r)$ else $error$}\\
+ \bl{$lex\,r\,c::s$} & \bl{$\dn$} & \bl{let $(r', frect) = simp(der(c, r))$}\smallskip\\
+ & & \bl{$inj\,r\,c\,(frect(lex(r', s)))$}\\
+\end{tabular}
+\end{center}\bigskip
-\end{frame}}
+\begin{center}\small
+\begin{tikzpicture}[node distance=1.1cm,every node/.style={minimum size=7mm}]
+\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}
+
+
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
+\frametitle{Records}
+
+\begin{itemize}
+\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause
-\mbox{\lstinputlisting[language=while]{../progs/collatz.while}}
+\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
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\small
+for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-
-\mbox{\lstinputlisting[language=while]{../progs/collatz.while}}
-
-\begin{textblock}{6}(10,2)
-\begin{tikzpicture}[scale=0.46]
-\begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs,
- xlabel=n,
- enlargelimits=0.05,
- ybar interval=0.7, legend style=small]
-\addplot file {interpreted2.data};
-\addplot file {compiled2.data};
-%\legend{interpreted, compiled}
-\end{axis}
-\end{tikzpicture}
-\end{textblock}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
+\frametitle{While Tokens}
-\begin{tikzpicture}[scale=1]
-
- \draw[line width=1mm] (-.3, 0) rectangle (1.5,2);
- \draw (4.2,1) node {Code Gen};
- \draw (0.6,1.7) node {\footnotesize Parser};
- \draw (-2.7,1.7) node {\footnotesize Lexer};
-
- \draw[line width=1mm] (-1.8, 0) rectangle (-3.6,2);
-
- \draw[white] (1.7,1) node (X) {};
- \draw[white] (3.2,1) node (Y) {};
- \draw[red, ->, line width = 2mm] (X) -- (Y);
-
- \draw[red, <-, line width = 2mm] (-0.6,1) -- (-1.6,1);
- \draw[red, <-, line width = 2mm] (-3.8,1) -- (-4.8,1);
-\end{tikzpicture}
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-\mode<presentation>{
-\begin{frame}[t]
-
-\consolas
\begin{center}
-"if true then then 42 else +"
+\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}
-
-\begin{tabular}{@{}l}
-KEYWORD: \\
-\hspace{5mm}{if}, {then}, {else},\\
-WHITESPACE:\\
-\hspace{5mm}{" "}, {$\backslash$n},\\
-IDENT:\\
-\hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + {\_})$^*$\\
-NUM:\\
-\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {0}\\
-OP:\\
-\hspace{5mm}{+}\\
-COMMENT:\\
-\hspace{5mm}{$\slash$*} $\cdot$ (ALL$^*$ $\cdot$ {*$\slash$} $\cdot$ ALL$^*$) $\cdot$ {*$\slash$}
-\end{tabular}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
@@ -430,72 +546,6 @@
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Nullable\end{tabular}}
-
-\small
-\ldots{}whether a regular expression can match the empty string:
-\begin{center}
-\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
-\bl{$nullable(\varnothing)$} & \bl{$\dn$} & \bl{$f\!\/alse$}\\
-\bl{$nullable(\epsilon)$} & \bl{$\dn$} & \bl{$true$}\\
-\bl{$nullable (c)$} & \bl{$\dn$} & \bl{$f\!alse$}\\
-\bl{$nullable (r_1 + r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \vee nullable(r_2)$} \\
-\bl{$nullable (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \wedge nullable(r_2)$} \\
-\bl{$nullable (r^*)$} & \bl{$\dn$} & \bl{$true$} \\
-\end{tabular}
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Zeroable\end{tabular}}
-
-\small
-\ldots{}whether a regular expression can match nothing:
-\begin{center}
-\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
-\bl{$zeroable(\varnothing)$} & \bl{$\dn$} & \bl{$true$}\\
-\bl{$zeroable(\epsilon)$} & \bl{$\dn$} & \bl{$f\!alse$}\\
-\bl{$zeroable (c)$} & \bl{$\dn$} & \bl{$f\!alse$}\\
-\bl{$zeroable (r_1 + r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \wedge zeroable(r_2)$} \\
-\bl{$zeroable (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \vee zeroable(r_2)$} \\
-\bl{$zeroable (r^*)$} & \bl{$\dn$} & \bl{$f\!alse$} \\
-\end{tabular}
-\end{center}\bigskip\pause
-
-\begin{center}
-\bl{$zeroable(r) \Leftrightarrow L(r) = \varnothing$}
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\begin{itemize}
-\item The star-case in our proof about the matcher needs the following lemma
-\begin{center}
-\bl{$Der\,c\,A^* = (Der\,c\,A)\,@\, A^*$}
-\end{center}
-\end{itemize}\bigskip\bigskip
-
-\begin{itemize}
-\item \bl{$A^* = \{""\} \cup A\,@\,A^*$}
-\item If \bl{\texttt{""} $\in A$}, then\\ \bl{$Der\,c\,(A @ B) = (Der\,c\,A) @ B \cup (Der\,c\,B)$}\medskip
-\item If \bl{\texttt{""} $\not\in A$}, then\\ \bl{$Der\,c\,(A @ B) = (Der\,c\,A) @ B$}
-
-\end{itemize}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}