diff -r 39aeca14af8c -r c22c8baff491 slides/slides05.tex --- 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{ \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{ -\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{ \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{ \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{ \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{ -\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{ -\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{ @@ -430,72 +546,6 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\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{ -\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{ -\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}