--- a/slides/slides02.tex Mon Sep 30 20:03:41 2013 +0100
+++ b/slides/slides02.tex Tue Oct 01 23:59:36 2013 +0100
@@ -134,6 +134,70 @@
28 34.79653
\end{filecontents}
+\begin{filecontents}{re1.data}
+1 0.00179
+2 0.00011
+3 0.00014
+4 0.00026
+5 0.00050
+6 0.00095
+7 0.00190
+8 0.00287
+9 0.00779
+10 0.01399
+11 0.01894
+12 0.03666
+13 0.07994
+14 0.08944
+15 0.02377
+16 0.07392
+17 0.22798
+18 0.65310
+19 2.11360
+20 6.31606
+21 21.46013
+\end{filecontents}
+
+\begin{filecontents}{re2a.data}
+1 0.00227
+5 0.00027
+10 0.00075
+15 0.00178
+20 0.00102
+25 0.00028
+30 0.00040
+35 0.00052
+40 0.00075
+45 0.00125
+50 0.00112
+55 0.00099
+60 0.00113
+65 0.00137
+70 0.00170
+\end{filecontents}
+
+\begin{filecontents}{re2b.data}
+1 0.00020
+51 0.00080
+101 0.00678
+151 0.01792
+201 0.04815
+251 0.09648
+301 0.23195
+351 0.52646
+401 0.96277
+451 1.57726
+501 2.00166
+551 2.98341
+601 4.81181
+651 6.57054
+701 9.73973
+751 14.25762
+801 14.80760
+851 19.60958
+901 25.43550
+951 31.96038
+\end{filecontents}
\begin{document}
@@ -216,12 +280,12 @@
\begin{textblock}{6}(2,6.5)
\begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
- \bl{r} & \bl{$::=$} & \bl{$\varnothing$} & null\\
+ \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$} & null\\
& \bl{$\mid$} & \bl{$\epsilon$} & empty string / {\consolas""} / $[]$\\
- & \bl{$\mid$} & \bl{c} & character\\
- & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$} & sequence\\
- & \bl{$\mid$} & \bl{r$_1$ + r$_2$} & alternative / choice\\
- & \bl{$\mid$} & \bl{r$^*$} & star (zero or more)\\
+ & \bl{$\mid$} & \bl{$c$} & character\\
+ & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\
+ & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\
+ & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\
\end{tabular}
\end{textblock}
@@ -319,13 +383,13 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}The Specification\\[-1mm] of Matching\end{tabular}}
+\frametitle{\begin{tabular}{c}The Specification\\[-1mm] for Matching\end{tabular}}
\large
-a regular expression \bl{r} matches a string \bl{s} is defined as
+a regular expression \bl{$r$} matches a string \bl{$s$}\\ if and only if
\begin{center}
-\bl{s $\in$ $L$(r)}\\
+\bl{$s \in L(r)$}\\
\end{center}\bigskip\bigskip\pause
\end{frame}}
@@ -356,11 +420,7 @@
%plots
\draw[color=blue] plot[mark=*, mark options={fill=white}]
file {re-python.data};
- \draw[color=red] plot[mark=triangle*, mark options={fill=white} ]
- file {re1.data};
- \draw[color=green] plot[mark=square*, mark options={fill=white} ]
- file {re2.data};
- \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ]
+ \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ]
file {re-ruby.data};
%legend
@@ -437,7 +497,7 @@
\frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}}
\large
-If \bl{r} matches the string \bl{c::s}, what is a regular expression that matches \bl{s}?\bigskip\bigskip\bigskip\bigskip
+If \bl{$r$} matches the string \bl{$c\!::\!s$}, what is a regular expression that matches \bl{$s$}?\bigskip\bigskip\bigskip\bigskip
\small
\bl{$der\,c\,r$} gives the answer
@@ -460,8 +520,8 @@
& & \bl{else $(der\, c\, r_1) \cdot r_2$}\\
\bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\smallskip\\\pause
- \bl{$der\!s\, [] r$} & \bl{$\dn$} & \bl{$r$} & \\
- \bl{$der\!s\, (c\!::\!s) r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\
+ \bl{$der\!s\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\
+ \bl{$der\!s\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\
\end{tabular}
\end{center}
@@ -483,12 +543,16 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}The Rexp Matcher\end{tabular}}
+\frametitle{\begin{tabular}{c}Examples\end{tabular}}
+Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
-{\lstset{language=Scala}\fontsize{8}{10}\selectfont
-\texttt{\lstinputlisting{../progs/app7.scala}}}
-
+\begin{center}
+\begin{tabular}{l}
+\bl{$der\,a\,r$}\\
+\bl{$der\,b\,r$}
+\end{tabular}
+\end{center}
\end{frame}}
@@ -497,22 +561,70 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Proofs about Rexp\end{tabular}}
+\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
+
+\mbox{}\\[-13mm]
+
+\begin{tikzpicture}[y=.2cm, x=.3cm]
+ %axis
+ \draw (0,0) -- coordinate (x axis mid) (30,0);
+ \draw (0,0) -- coordinate (y axis mid) (0,30);
+ %ticks
+ \foreach \x in {0,5,...,30}
+ \draw (\x,1pt) -- (\x,-3pt)
+ node[anchor=north] {\x};
+ \foreach \y in {0,5,...,30}
+ \draw (1pt,\y) -- (-3pt,\y)
+ node[anchor=east] {\y};
+ %labels
+ \node[below=0.6cm] at (x axis mid) {\bl{a}s};
+ \node[rotate=90, left=1.2cm] at (y axis mid) {secs};
+
+ %plots
+ \draw[color=blue] plot[mark=*, mark options={fill=white}]
+ file {re-python.data};
+ \draw[color=red] plot[mark=triangle*, mark options={fill=white} ]
+ file {re1.data};
+ \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ]
+ file {re-ruby.data};
+
+
+ %legend
+ \begin{scope}[shift={(4,20)}]
+ \draw[color=blue] (0,0) --
+ plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0)
+ node[right]{\small Python};
+ \draw[yshift=-\baselineskip, color=brown] (0,0) --
+ plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)
+ node[right]{\small Ruby};
+ \draw[yshift=\baselineskip, color=red] (0,0) --
+ plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)
+ node[right]{\small Scala V1};
+ \end{scope}
+\end{tikzpicture}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Proofs about Rexps\end{tabular}}
Remember their inductive definition:\\[5cm]
\begin{textblock}{6}(5,5)
\begin{tabular}{@ {}rrl}
- \bl{r} & \bl{$::=$} & \bl{$\varnothing$}\\
+ \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$^*$} \\
+ & \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{textblock}
-If we want to prove something, say a property \bl{$P$(r)}, for all regular expressions \bl{r} then \ldots
+If we want to prove something, say a property \bl{$P(r)$}, for all regular expressions \bl{$r$} then \ldots
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -524,12 +636,12 @@
\begin{itemize}
\item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} 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$}.
-\item \bl{$P$} holds for \bl{r$^*$} under the assumption that \bl{$P$} already
-holds for \bl{r}.
+\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}}
@@ -543,7 +655,7 @@
Assume \bl{$P(r)$} is the property:
\begin{center}
-\bl{nullable(r)} if and only if \bl{"" $\in$ $L$(r)}
+\bl{$nullable(r)$} if and only if \bl{$"" \in L(r)$}
\end{center}
\end{frame}}
@@ -552,14 +664,37 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Proofs about Rexp (4)\end{tabular}}
+
+Let \bl{$Der\,c\,A$} be the set defined as
+
+\begin{center}
+\bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ }
+\end{center}
+
+We can prove
+
+\begin{center}
+\bl{$L(der\,c\,r) = Der\,c\,(L(r))$}
+\end{center}
+
+by induction on \bl{$r$}.
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
\frametitle{\begin{tabular}{c}Proofs about Strings\end{tabular}}
-If we want to prove something, say a property \bl{$P$(s)}, for all strings \bl{s} then \ldots\bigskip
+If we want to prove something, say a property \bl{$P(s)$}, for all strings \bl{$s$} then \ldots\bigskip
\begin{itemize}
\item \bl{$P$} holds for the empty string, and\medskip
-\item \bl{$P$} holds for the string \bl{c::s} under the assumption that \bl{$P$}
-already holds for \bl{s}
+\item \bl{$P$} holds for the string \bl{$c\!::\!s$} under the assumption that \bl{$P$}
+already holds for \bl{$s$}
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -569,16 +704,10 @@
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Proofs about Strings (2)\end{tabular}}
-Let \bl{Der c A} be the set defined as
+We can finally prove
\begin{center}
-\bl{Der c A $\dn$ $\{$ s $|$ c::s $\in$ A$\}$ }
-\end{center}
-
-Assume that \bl{$L$(der c r) = Der c ($L$(r))}. Prove that
-
-\begin{center}
-\bl{matcher(r, s) if and only if s $\in$ $L$(r)}
+\bl{$matcher(r, s)$} if and only if \bl{$s \in L(r)$}
\end{center}
@@ -587,6 +716,179 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
+
+\mbox{}\\[-13mm]
+
+\begin{tikzpicture}[y=.2cm, x=.3cm]
+ %axis
+ \draw (0,0) -- coordinate (x axis mid) (30,0);
+ \draw (0,0) -- coordinate (y axis mid) (0,30);
+ %ticks
+ \foreach \x in {0,5,...,30}
+ \draw (\x,1pt) -- (\x,-3pt)
+ node[anchor=north] {\x};
+ \foreach \y in {0,5,...,30}
+ \draw (1pt,\y) -- (-3pt,\y)
+ node[anchor=east] {\y};
+ %labels
+ \node[below=0.6cm] at (x axis mid) {\bl{a}s};
+ \node[rotate=90, left=1.2cm] at (y axis mid) {secs};
+
+ %plots
+ \draw[color=blue] plot[mark=*, mark options={fill=white}]
+ file {re-python.data};
+ \draw[color=red] plot[mark=triangle*, mark options={fill=white} ]
+ file {re1.data};
+ \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ]
+ file {re-ruby.data};
+
+
+ %legend
+ \begin{scope}[shift={(4,20)}]
+ \draw[color=blue] (0,0) --
+ plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0)
+ node[right]{\small Python};
+ \draw[yshift=-\baselineskip, color=brown] (0,0) --
+ plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)
+ node[right]{\small Ruby};
+ \draw[yshift=\baselineskip, color=red] (0,0) --
+ plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)
+ node[right]{\small Scala V1};
+ \end{scope}
+\end{tikzpicture}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Problem\end{tabular}}
+
+We represented ``n-times'' as a sequence regular expression:
+
+\begin{center}
+\begin{tabular}{ll}
+1:
+\end{tabular}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
+
+\mbox{}\\[-13mm]
+
+\begin{tikzpicture}[y=.2cm, x=.12cm]
+ %axis
+ \draw (0,0) -- coordinate (x axis mid) (70,0);
+ \draw (0,0) -- coordinate (y axis mid) (0,30);
+ %ticks
+ \foreach \x in {0,10,...,70}
+ \draw (\x,1pt) -- (\x,-3pt)
+ node[anchor=north] {\x};
+ \foreach \y in {0,5,...,30}
+ \draw (1pt,\y) -- (-3pt,\y)
+ node[anchor=east] {\y};
+ %labels
+ \node[below=0.6cm] at (x axis mid) {\bl{a}s};
+ \node[rotate=90, left=1.2cm] at (y axis mid) {secs};
+
+ %plots
+ \draw[color=blue] plot[mark=*, mark options={fill=white}]
+ file {re-python.data};
+ \draw[color=red] plot[mark=triangle*, mark options={fill=white} ]
+ file {re1.data};
+ \draw[color=green] plot[mark=square*, mark options={fill=white} ]
+ file {re2a.data};
+ \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ]
+ file {re-ruby.data};
+
+ %legend
+ \begin{scope}[shift={(4,20)}]
+ \draw[color=blue] (0,0) --
+ plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0)
+ node[right]{\small Python};
+ \draw[yshift=-\baselineskip, color=brown] (0,0) --
+ plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)
+ node[right]{\small Ruby};
+ \draw[yshift=\baselineskip, color=red] (0,0) --
+ plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)
+ node[right]{\small Scala V1};
+ \draw[yshift=2\baselineskip, color=green] (0,0) --
+ plot[mark=square*, mark options={fill=white}] (0.25,0) -- (0.5,0)
+ node[right]{\small Scala V2};
+ \end{scope}
+\end{tikzpicture}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
+
+\mbox{}\\[-13mm]
+
+\begin{tabular}{@ {\hspace{-5mm}}l}
+\begin{tikzpicture}[y=.2cm, x=.01cm]
+ %axis
+ \draw (0,0) -- coordinate (x axis mid) (1000,0);
+ \draw (0,0) -- coordinate (y axis mid) (0,30);
+ %ticks
+ \foreach \x in {0,100,...,1000}
+ \draw (\x,1pt) -- (\x,-3pt)
+ node[anchor=north] {\x};
+ \foreach \y in {0,5,...,30}
+ \draw (1pt,\y) -- (-3pt,\y)
+ node[anchor=east] {\y};
+ %labels
+ \node[below=0.6cm] at (x axis mid) {\bl{a}s};
+ \node[rotate=90, left=1.2cm] at (y axis mid) {secs};
+
+ %plots
+ \draw[color=blue] plot[mark=*, mark options={fill=white}]
+ file {re-python.data};
+ \draw[color=red] plot[mark=triangle*, mark options={fill=white} ]
+ file {re1.data};
+ \draw[color=green] plot[mark=square*, mark options={fill=white} ]
+ file {re2b.data};
+ \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ]
+ file {re-ruby.data};
+
+ %legend
+ \begin{scope}[shift={(100,20)}]
+ \draw[color=blue] (0,0) --
+ plot[mark=*, mark options={fill=white}] (0.25,0) -- (50,0)
+ node[right]{\small Python};
+ \draw[yshift=-13, color=brown] (0,0) --
+ plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (50,0)
+ node[right]{\small Ruby};
+ \draw[yshift=13, color=red] (0,0) --
+ plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (50,0)
+ node[right]{\small Scala V1};
+ \draw[yshift=26, color=green] (0,0) --
+ plot[mark=square*, mark options={fill=white}] (0.25,0) -- (50,0)
+ node[right]{\small Scala V2};
+ \end{scope}
+\end{tikzpicture}
+\end{tabular}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Regular Languages\end{tabular}}
@@ -618,6 +920,22 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}The Rexp Matcher\end{tabular}}
+
+
+{\lstset{language=Scala}\fontsize{8}{10}\selectfont
+\texttt{\lstinputlisting{../progs/app7.scala}}}
+
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
\end{document}
%%% Local Variables: