--- a/slides/slides04.tex Tue Oct 15 22:14:04 2013 +0100
+++ b/slides/slides04.tex Wed Oct 16 02:07:02 2013 +0100
@@ -18,6 +18,9 @@
\usetikzlibrary{shadows}
\usetikzlibrary{positioning}
\usetikzlibrary{calc}
+\usetikzlibrary{fit}
+\usetikzlibrary{plotmarks}
+\usetikzlibrary{backgrounds}
\usepackage{graphicx}
\definecolor{javared}{rgb}{0.6,0,0} % for strings
@@ -25,8 +28,13 @@
\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords
\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc
+\makeatletter
+\lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}}
+\@empty\z@\@empty
+\makeatother
+
\lstset{language=Java,
- basicstyle=\ttfamily,
+ basicstyle=\consolas,
keywordstyle=\color{javapurple}\bfseries,
stringstyle=\color{javagreen},
commentstyle=\color{javagreen},
@@ -47,7 +55,7 @@
private,protected,requires,return,sealed,%
super,this,throw,trait,true,try,%
type,val,var,while,with,yield},
- otherkeywords={=>,<-,<\%,<:,>:,\#,@},
+ otherkeywords={=>,<-,<\%,<:,>:,\#,@,->},
sensitive=true,
morecomment=[l]{//},
morecomment=[n]{/*}{*/},
@@ -57,7 +65,7 @@
}
\lstset{language=Scala,
- basicstyle=\ttfamily,
+ basicstyle=\consolas,
keywordstyle=\color{javapurple}\bfseries,
stringstyle=\color{javagreen},
commentstyle=\color{javagreen},
@@ -69,12 +77,113 @@
tabsize=2,
showspaces=false,
showstringspaces=false}
-
+
% beamer stuff
\renewcommand{\slidecaption}{AFL 04, King's College London, 16.~October 2013}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
+% The data files, written on the first run.
+\begin{filecontents}{re-python.data}
+1 0.029
+5 0.029
+10 0.029
+15 0.032
+16 0.042
+17 0.042
+18 0.055
+19 0.084
+20 0.136
+21 0.248
+22 0.464
+23 0.899
+24 1.773
+25 3.505
+26 6.993
+27 14.503
+28 29.307
+#29 58.886
+\end{filecontents}
+
+\begin{filecontents}{re-ruby.data}
+1 0.00006
+2 0.00003
+3 0.00001
+4 0.00001
+5 0.00001
+6 0.00002
+7 0.00002
+8 0.00004
+9 0.00007
+10 0.00013
+11 0.00026
+12 0.00055
+13 0.00106
+14 0.00196
+15 0.00378
+16 0.00764
+17 0.01606
+18 0.03094
+19 0.06508
+20 0.12420
+21 0.25393
+22 0.51449
+23 1.02174
+24 2.05998
+25 4.22514
+26 8.42479
+27 16.88678
+28 34.79653
+\end{filecontents}
+
+\begin{filecontents}{nfa.data}
+0 0.00099
+5 0.01304
+10 0.05350
+15 0.10152
+20 0.10876
+25 0.06984
+30 0.09693
+35 0.04805
+40 0.07512
+45 0.07624
+50 0.10451
+55 0.13285
+60 0.15748
+65 0.19982
+70 0.24075
+75 0.28963
+80 0.35734
+85 0.43735
+90 0.49692
+95 0.59551
+100 0.72236
+\end{filecontents}
+
+\begin{filecontents}{nfasearch.data}
+0 0.00009
+1 0.00147
+2 0.00030
+3 0.00062
+4 0.00132
+5 0.00177
+6 0.00487
+7 0.00947
+8 0.01757
+9 0.02050
+10 0.02091
+11 0.04002
+12 0.08662
+13 0.17269
+14 0.37255
+15 0.81935
+16 1.76254
+17 3.89442
+18 8.42263
+19 17.89661
+20 38.21481
+\end{filecontents}
+
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -122,6 +231,572 @@
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}DFAs\end{tabular}}
+
+A deterministic finite automaton consists of:
+
+\begin{itemize}
+\item a finite set of states, \bl{$Q$}
+\item one of these states is the start state, \bl{$q_0$}
+\item there is transition function, \bl{$\delta$}, and
+\item some states are accepting states, \bl{$F$}
+\medskip
+\end{itemize}
+
+\begin{center}
+\bl{$A(Q, q_0, \delta, F)$}
+\end{center}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}State Nodes\end{tabular}}
+
+\hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont
+\lstinputlisting{../progs/appA.scala}}}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}DFAs\;\;\;\end{tabular}}
+
+\mbox{}\\[7mm]
+
+\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont
+\lstinputlisting{../progs/appB.scala}}}
+
+\only<2->{
+\begin{textblock}{9}(7.5,0.5)
+\begin{tikzpicture}
+\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
+{\normalsize\color{darkgray}
+\begin{minipage}{6cm}
+\begin{tabular}{l}
+\bl{$\hat{\delta}(q, \texttt{""}) \dn q$}\\
+\bl{$\hat{\delta}(q, c::s) \dn \hat{\delta}(\delta(q, c), s)$}\\[4mm]
+\bl{$\hat{\delta}(q_0, s) \in F$}
+\end{tabular}
+\end{minipage}};
+\end{tikzpicture}
+\end{textblock}}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+
+\mbox{}\hspace{-10mm}
+\begin{tikzpicture}[scale=0.6,>=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}
+
+\only<1->{
+\begin{textblock}{9}(7.4,3.5)
+\begin{tikzpicture}
+\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
+{\normalsize\color{darkgray}
+\begin{minipage}{6.6cm}
+\hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{8}{10}\selectfont
+\lstinputlisting{../progs/appC.scala}}}
+\end{minipage}};
+\end{tikzpicture}
+\end{textblock}}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}NFAs\end{tabular}}
+
+A non-deterministic finite automaton \bl{$A(Q, q_0, \delta, F)$} consists of:\medskip
+
+\begin{itemize}
+\item a finite set of states, \bl{$Q$}
+\item one of these states is the start state, \bl{$q_0$}
+\item some states are accepting states, \bl{$F$},
+\item there is transition \alert{relation}, \bl{$\delta$}, and
+\item there are \alert{silent} transitions\medskip
+\end{itemize}
+
+
+\begin{center}
+\begin{tabular}{c}
+\bl{$(q_1, a) \rightarrow q_2$}\\
+\bl{$(q_1, a) \rightarrow q_3$}\\
+\end{tabular}
+\hspace{10mm}
+\begin{tabular}{c}
+\bl{$(q_1, \epsilon) \rightarrow q_2$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont
+\lstinputlisting{../progs/appD.scala}}}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+
+\mbox{}\hspace{-10mm}
+\begin{tikzpicture}[scale=0.6,>=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) [above=of q_0] {$q_1$};
+\node[state, accepting] (q_2) [below=of q_0] {$q_2$};
+\path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_1);
+\path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_2);
+\path[->] (q_0) edge [loop right] node {\alert{$a$}} ();
+\path[->] (q_1) edge [loop above] node {\alert{$a$}} ();
+\path[->] (q_2) edge [loop below] node {\alert{$b$}} ();
+\end{tikzpicture}
+
+\only<1->{
+\begin{textblock}{9}(6,1.5)
+\begin{tikzpicture}
+\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
+{\normalsize\color{darkgray}
+\begin{minipage}{7cm}
+\hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{8}{10}\selectfont
+\lstinputlisting{../progs/appE.scala}}}
+\end{minipage}};
+\end{tikzpicture}
+\end{textblock}}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{Rexp to NFA}
+
+Thompson's construction of a NFA from a regular expression:
+
+\begin{center}
+\begin{tabular}[t]{l@{\hspace{10mm}}l}
+\raisebox{1mm}{\bl{$\varnothing$}} &
+\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
+\node[state, initial] (q_0) {$\mbox{}$};
+\end{tikzpicture}\\\\
+\raisebox{1mm}{\bl{$\epsilon$}} &
+\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
+\node[state, initial, accepting] (q_0) {$\mbox{}$};
+\end{tikzpicture}\\\\
+\raisebox{2mm}{\bl{$c$}} &
+\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
+\node[state, initial] (q_0) {$\mbox{}$};
+\node[state, accepting] (q_1) [right=of q_0] {$\mbox{}$};
+\path[->] (q_0) edge node [below] {\alert{$c$}} (q_1);
+\end{tikzpicture}\\\\
+\end{tabular}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{Case $r_1\cdot r_2$}
+
+\mbox{}\bigskip
+\onslide<1>{By recursion we are given two automata:\bigskip}
+
+{\centering\begin{tikzpicture}[node distance=3mm,
+ >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
+\node[state, initial] (q_0) {$\mbox{}$};
+\node (r_1) [right=of q_0] {$\ldots$};
+\only<1>{
+\node[state, accepting] (t_1) [right=of r_1] {$\mbox{}$};
+\node[state, accepting] (t_2) [above=of t_1] {$\mbox{}$};
+\node[state, accepting] (t_3) [below=of t_1] {$\mbox{}$};}
+\only<2>{
+\node[state] (t_1) [right=of r_1] {$\mbox{}$};
+\node[state] (t_2) [above=of t_1] {$\mbox{}$};
+\node[state] (t_3) [below=of t_1] {$\mbox{}$};}
+\only<1>{\node[state, initial] (a_0) [right=2.5cm of t_1] {$\mbox{}$};}
+\only<2>{\node[state] (a_0) [right=2.5cm of t_1] {$\mbox{}$};}
+\node (b_1) [right=of a_0] {$\ldots$};
+\node[state, accepting] (c_1) [right=of b_1] {$\mbox{}$};
+\node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$};
+\node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$};
+\only<2>{
+\path[->] (t_1) edge node [above, pos=0.3] {\alert{$\epsilon$}} (a_0);
+\path[->] (t_2) edge node [above] {\alert{$\epsilon$}} (a_0);
+\path[->] (t_3) edge node [below] {\alert{$\epsilon$}} (a_0);
+}
+\begin{pgfonlayer}{background}
+\only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (r_1) (t_1) (t_2) (t_3)] {};}
+\only<1>{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (a_0) (b_1) (c_1) (c_2) (c_3)] {};}
+\only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (c_1) (c_2) (c_3)] {};}
+\only<1>{\node [yshift=2mm] at (1.north) {\bl{$r_1$}};}
+\only<1>{\node [yshift=2mm] at (2.north) {\bl{$r_2$}};}
+\only<2>{\node [yshift=2mm] at (3.north) {\bl{$r_1\cdot r_2$}};}
+\end{pgfonlayer}
+\end{tikzpicture}}\bigskip\bigskip
+
+\small
+We need to (1) change the accepting nodes of the first automaton into non-accepting nodes, and (2) connect them
+via $\epsilon$-transitions to the starting state of the second automaton.
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{Case $r_1+ r_2$}
+
+\onslide<1>{By recursion we are given two automata:\smallskip}
+
+\hspace{2cm}\begin{tikzpicture}[node distance=3mm,
+ >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
+\onslide<1>{\node at (0,0) (1) {$\mbox{}$};}
+\onslide<2>{\node at (0,0) [state, initial] (1) {$\mbox{}$};}
+\only<1>{
+\node[state, initial] (2) [above right=16mm of 1] {$\mbox{}$};
+\node[state, initial] (3) [below right=16mm of 1] {$\mbox{}$};}
+\only<2>{
+\node[state] (2) [above right=16mm of 1] {$\mbox{}$};
+\node[state] (3) [below right=16mm of 1] {$\mbox{}$};}
+
+\node (a) [right=of 2] {$\ldots$};
+\node[state, accepting] (a1) [right=of a] {$\mbox{}$};
+\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
+\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};
+
+\node (b) [right=of 3] {$\ldots$};
+\node[state, accepting] (b1) [right=of b] {$\mbox{}$};
+\node[state, accepting] (b2) [above=of b1] {$\mbox{}$};
+\node[state, accepting] (b3) [below=of b1] {$\mbox{}$};
+\only<2>{
+\path[->] (1) edge node [above] {\alert{$\epsilon$}} (2);
+\path[->] (1) edge node [below] {\alert{$\epsilon$}} (3);
+}
+\begin{pgfonlayer}{background}
+\only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};}
+\only<1>{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (3) (b1) (b2) (b3)] {};}
+\only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3) (b2) (b3)] {};}
+\only<1>{\node [yshift=3mm] at (1.north) {\bl{$r_1$}};}
+\only<1>{\node [yshift=3mm] at (2.north) {\bl{$r_2$}};}
+\only<2>{\node [yshift=3mm] at (3.north) {\bl{$r_1+ r_2$}};}
+\end{pgfonlayer}
+\end{tikzpicture}
+
+\small
+We (1) need to introduce a new starting state and (2) connect it to the original two starting states.
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{Case $r^*$}
+
+\onslide<1>{By recursion we are given an automaton for $r$:\smallskip}
+
+\hspace{2cm}\begin{tikzpicture}[node distance=3mm,
+ >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
+\onslide<1>{\node at (0,0) (1) {$\mbox{}$};}
+\onslide<2->{\node at (0,0) [state, initial,accepting] (1) {$\mbox{}$};}
+\only<1>{\node[state, initial] (2) [right=16mm of 1] {$\mbox{}$};}
+\only<2->{\node[state] (2) [right=16mm of 1] {$\mbox{}$};}
+\node (a) [right=of 2] {$\ldots$};
+\only<1>{
+\node[state, accepting] (a1) [right=of a] {$\mbox{}$};
+\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
+\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};}
+\only<2->{
+\node[state] (a1) [right=of a] {$\mbox{}$};
+\node[state] (a2) [above=of a1] {$\mbox{}$};
+\node[state] (a3) [below=of a1] {$\mbox{}$};}
+\only<2->{
+\path[->] (1) edge node [above] {\alert{$\epsilon$}} (2);
+\path[->] (a1) edge [bend left=45] node [above] {\alert{$\epsilon$}} (1);
+\path[->] (a2) edge [bend right] node [below] {\alert{$\epsilon$}} (1);
+\path[->] (a3) edge [bend left=45] node [below] {\alert{$\epsilon$}} (1);
+
+}
+\begin{pgfonlayer}{background}
+\only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};}
+\only<2->{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};}
+\only<1>{\node [yshift=3mm] at (1.north) {\bl{$r$}};}
+\only<2->{\node [yshift=3mm] at (2.north) {\bl{$r^*$}};}
+\end{pgfonlayer}
+\end{tikzpicture}\bigskip
+
+\onslide<3->{
+Why can't we just have an epsilon transition from the accepting states to the starting state?}
+
+\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=.09cm]
+ %axis
+ \draw (0,0) -- coordinate (x axis mid) (100,0);
+ \draw (0,0) -- coordinate (y axis mid) (0,30);
+ %ticks
+ \foreach \x in {0,10,...,100}
+ \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 {nfa.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 NFA 1};
+ \end{scope}
+\end{tikzpicture}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{Greedy Depth-First}
+
+\hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont
+\lstinputlisting{../progs/appG.scala}}}
+
+\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=.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 {nfasearch.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 NFA 2};
+ \end{scope}
+\end{tikzpicture}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}<2>[c]
+\frametitle{DFA to Rexp}
+
+\begin{center}
+\begin{tikzpicture}[scale=2, line width=0.5mm]
+ \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] {$a$} (q1)
+ (q1) edge[bend left] node[above] {$b$} (q0)
+ (q2) edge[bend left=50] node[below] {$b$} (q0)
+ (q1) edge node[above] {$a$} (q2)
+ (q2) edge [loop right] node {$a$} ()
+ (q0) edge [loop below] node {$b$} ()
+ ;
+\end{tikzpicture}
+\end{center}
+
+\onslide<3>{How to get from a DFA to a regular expression?}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\begin{tikzpicture}[scale=2, line width=0.5mm]
+ \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};}
+ \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};}
+ \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};}
+ \path[->] (q0) edge[bend left] node[above] {$a$} (q1)
+ (q1) edge[bend left] node[above] {$b$} (q0)
+ (q2) edge[bend left=50] node[below] {$b$} (q0)
+ (q1) edge node[above] {$a$} (q2)
+ (q2) edge [loop right] node {$a$} ()
+ (q0) edge [loop below] node {$b$} ()
+ ;
+\end{tikzpicture}
+\end{center}\pause\bigskip
+
+\onslide<2->{
+\begin{center}
+\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
+\bl{$q_0$} & \bl{$=$} & \bl{$2\, q_0 + 3 \,q_1 + 4\, q_2$}\\
+\bl{$q_1$} & \bl{$=$} & \bl{$2 \,q_0 + 3\, q_1 + 1\, q_2$}\\
+\bl{$q_2$} & \bl{$=$} & \bl{$1\, q_0 + 5\, q_1 + 2\, q_2$}\\
+
+\end{tabular}
+\end{center}
+}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\begin{tikzpicture}[scale=2, line width=0.5mm]
+ \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};}
+ \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};}
+ \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};}
+ \path[->] (q0) edge[bend left] node[above] {$a$} (q1)
+ (q1) edge[bend left] node[above] {$b$} (q0)
+ (q2) edge[bend left=50] node[below] {$b$} (q0)
+ (q1) edge node[above] {$a$} (q2)
+ (q2) edge [loop right] node {$a$} ()
+ (q0) edge [loop below] node {$b$} ()
+ ;
+\end{tikzpicture}
+\end{center}\bigskip
+
+\onslide<2->{
+\begin{center}
+\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
+\bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b + q_2\,b$}\\
+\bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\
+\bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\
+
+\end{tabular}
+\end{center}
+}
+
+\onslide<3->{
+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}
+
+\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
+\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 chance.
+\item All unmarked pairs can be merged.
+\end{enumerate}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -146,7 +821,7 @@
\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}
+\end{center}\pause
\mbox{}\\[-20mm]\mbox{}
@@ -168,532 +843,19 @@
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\begin{enumerate}
-\item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p}
-\item Mark all pairs that are accepting and non-accepting states
-\item For all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether
-\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 chance.
-\item All unmarked pairs can be merged.
-\end{enumerate}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Last Week\end{tabular}}
-
-Last week I showed you\bigskip
-
-\begin{itemize}
-\item a tokenizer taking a list of regular expressions\bigskip
-
-\item tokenization identifies lexeme in an input stream of characters (or string)
-and cathegorizes them into tokens
-
-\end{itemize}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Two Rules\end{tabular}}
-
-\begin{itemize}
-\item Longest match rule (maximal munch rule): The
-longest initial substring matched by any regular expression is taken
-as next token.\bigskip
-
-\item Rule priority:
-For a particular longest initial substring, the first regular
-expression that can match determines the token.
-
-\end{itemize}
-
-%\url{http://www.technologyreview.com/tr10/?year=2011}
-
-%finite deterministic automata/ nondeterministic automaton
-
-%\item problem with infix operations, for example i-12
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-\mode<presentation>{
-\begin{frame}[t]
-
-\begin{center}
-\texttt{"if true then then 42 else +"}
-\end{center}
-
-
-\begin{tabular}{@{}l}
-KEYWORD: \\
-\hspace{5mm}\texttt{"if"}, \texttt{"then"}, \texttt{"else"},\\
-WHITESPACE:\\
-\hspace{5mm}\texttt{" "}, \texttt{"$\backslash$n"},\\
-IDENT:\\
-\hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + \texttt{"\_"})$^*$\\
-NUM:\\
-\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + \texttt{"0"}\\
-OP:\\
-\hspace{5mm}\texttt{"+"}\\
-COMMENT:\\
-\hspace{5mm}\texttt{"$\slash$*"} $\cdot$ (ALL$^*$ $\cdot$ \texttt{"*$\slash$"} $\cdot$ ALL$^*$) $\cdot$ \texttt{"*$\slash$"}
-\end{tabular}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-
-\begin{center}
-\texttt{"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}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-
-There is one small problem with the tokenizer. How should we
-tokenize:
-
-\begin{center}
-\texttt{"x - 3"}
-\end{center}
-
-\begin{tabular}{@{}l}
-OP:\\
-\hspace{5mm}\texttt{"+"}, \texttt{"-"}\\
-NUM:\\
-\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + \texttt{"0"}\\
-NUMBER:\\
-\hspace{5mm}NUM + (\texttt{"-"} $\cdot$ NUM)\\
-\end{tabular}
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Negation\end{tabular}}
-
-Assume you have an alphabet consisting of the letters \bl{a}, \bl{b} and \bl{c} only.
-Find a regular expression that matches all strings \emph{except} \bl{ab}, \bl{ac} and \bl{cba}.
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Deterministic Finite Automata\end{tabular}}
-
-A deterministic finite automaton consists of:
-
-\begin{itemize}
-\item a finite set of states
-\item one of these states is the start state
-\item some states are accepting states, and
-\item there is transition function\medskip
-
-\small
-which takes a state and a character as arguments and produces a new state\smallskip\\
-this function might not always be defined everywhere
-\end{itemize}
-
-\begin{center}
-\bl{$A(Q, q_0, F, \delta)$}
-\end{center}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\begin{center}
-\includegraphics[scale=0.7]{pics/ch3.jpg}
-\end{center}\pause
-
-\begin{itemize}
-\item start can be an accepting state
-\item it is possible that there is no accepting state
-\item all states might be accepting (but does not necessarily mean all strings are accepted)
-\end{itemize}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\begin{center}
-\includegraphics[scale=0.7]{pics/ch3.jpg}
-\end{center}
-
-for this automaton \bl{$\delta$} is the function\\
-
-\begin{center}
-\begin{tabular}{lll}
-\bl{(q$_0$, a) $\rightarrow$ q$_1$} & \bl{(q$_1$, a) $\rightarrow$ q$_4$} & \bl{(q$_4$, a) $\rightarrow$ q$_4$}\\
-\bl{(q$_0$, b) $\rightarrow$ q$_2$} & \bl{(q$_1$, b) $\rightarrow$ q$_2$} & \bl{(q$_4$, b) $\rightarrow$ q$_4$}\\
-\end{tabular}\ldots
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Accepting a String\end{tabular}}
-
-Given
-
-\begin{center}
-\bl{$A(Q, q_0, F, \delta)$}
-\end{center}
-
-you can define
-
-\begin{center}
-\begin{tabular}{l}
-\bl{$\hat{\delta}(q, \texttt{""}) = q$}\\
-\bl{$\hat{\delta}(q, c::s) = \hat{\delta}(\delta(q, c), s)$}\\
-\end{tabular}
-\end{center}\pause
-
-Whether a string \bl{$s$} is accepted by \bl{$A$}?
-
-\begin{center}
-\hspace{5mm}\bl{$\hat{\delta}(q_0, s) \in F$}
-\end{center}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Non-Deterministic\\[-1mm] Finite Automata\end{tabular}}
-
-A non-deterministic finite automaton consists again of:
-
-\begin{itemize}
-\item a finite set of states
-\item one of these states is the start state
-\item some states are accepting states, and
-\item there is transition \alert{relation}\medskip
-\end{itemize}
-
-
-\begin{center}
-\begin{tabular}{c}
-\bl{(q$_1$, a) $\rightarrow$ q$_2$}\\
-\bl{(q$_1$, a) $\rightarrow$ q$_3$}\\
-\end{tabular}
-\hspace{10mm}
-\begin{tabular}{c}
-\bl{(q$_1$, $\epsilon$) $\rightarrow$ q$_2$}\\
-\end{tabular}
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\begin{center}
-\includegraphics[scale=0.7]{pics/ch5.jpg}
-\end{center}
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\begin{center}
-\begin{tabular}[b]{ll}
-\bl{$\varnothing$} & \includegraphics[scale=0.7]{pics/NULL.jpg}\\\\
-\bl{$\epsilon$} & \includegraphics[scale=0.7]{pics/epsilon.jpg}\\\\
-\bl{c} & \includegraphics[scale=0.7]{pics/char.jpg}\\
-\end{tabular}
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\begin{center}
-\begin{tabular}[t]{ll}
-\bl{r$_1$ $\cdot$ r$_2$} & \includegraphics[scale=0.6]{pics/seq.jpg}\\\\
-\end{tabular}
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\begin{center}
-\begin{tabular}[t]{ll}
-\bl{r$_1$ + r$_2$} & \includegraphics[scale=0.7]{pics/alt.jpg}\\\\
-\end{tabular}
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\begin{center}
-\begin{tabular}[b]{ll}
-\bl{r$^*$} & \includegraphics[scale=0.7]{pics/star.jpg}\\
-\end{tabular}
-\end{center}\pause\bigskip
-
-Why can't we just have an epsilon transition from the accepting states to the starting state?
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Subset Construction\end{tabular}}
-
-
-\begin{textblock}{5}(1,2.5)
-\includegraphics[scale=0.5]{pics/ch5.jpg}
-\end{textblock}
-
-\begin{textblock}{11}(6.5,4.5)
-\begin{tabular}{r|cl}
-& a & b\\
-\hline
-$\varnothing$ \onslide<2>{\textcolor{white}{*}} & $\varnothing$ & $\varnothing$\\
-$\{0\}$ \onslide<2>{\textcolor{white}{*}} & $\{0,1,2\}$ & $\{2\}$\\
-$\{1\}$ \onslide<2>{\textcolor{white}{*}} &$\{1\}$ & $\varnothing$\\
-$\{2\}$ \onslide<2>{*} & $\varnothing$ &$\{2\}$\\
-$\{0,1\}$ \onslide<2>{\textcolor{white}{*}} &$\{0,1,2\}$ &$\{2\}$\\
-$\{0,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\
-$\{1,2\}$ \onslide<2>{*}& $\{1\}$ & $\{2\}$\\
-\onslide<2>{s:} $\{0,1,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\
-\end{tabular}
-\end{textblock}
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Regular Languages\end{tabular}}
-
-A language is \alert{regular} iff there exists
-a regular expression that recognises all its strings.\bigskip\medskip
-
-or equivalently\bigskip\medskip
-
-A language is \alert{regular} iff there exists
-a deterministic finite automaton that recognises all its strings.\bigskip\pause
-
-Why is every finite set of strings a regular language?
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\begin{center}
-\includegraphics[scale=0.5]{pics/ch3.jpg}
-\end{center}
-
-\begin{center}
-\includegraphics[scale=0.5]{pics/ch4.jpg}\\
-minimal automaton
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\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
-\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 chance.
-\item All unmarked pairs can be merged.
-\end{enumerate}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-Given the function
-
-\begin{center}
-\bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
-$rev(\varnothing)$ & $\dn$ & $\varnothing$\\
-$rev(\epsilon)$ & $\dn$ & $\epsilon$\\
-$rev(c)$ & $\dn$ & $c$\\
-$rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\
-$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\
-$rev(r^*)$ & $\dn$ & $rev(r)^*$\\
-\end{tabular}}
-\end{center}
-
-
-and the set
-
-\begin{center}
-\bl{$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$}
-\end{center}
-
-prove whether
-
-\begin{center}
-\bl{$L(rev(r)) = Rev (L(r))$}
-\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 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}
-
+\item Assuming you have the alphabet \bl{$\{a, b, c\}$}\bigskip
+\item Give a regular expression that can recognise all strings that have at least one \bl{$b$}.
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\begin{itemize}
-\item Assuming you have the alphabet \bl{\{a, b, c\}}\bigskip
-\item Give a regular expression that can recognise all strings that have at least one \bl{b}.
-\end{itemize}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-``I hate coding. I do not want to look at code.''
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
\end{document}
%%% Local Variables: