--- a/slides/slides04.tex Sat Oct 11 13:54:18 2014 +0100
+++ b/slides/slides04.tex Sun Oct 12 19:39:55 2014 +0100
@@ -32,11 +32,9 @@
\end{tabular}
\end{center}
\end{frame}
- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
\frametitle{Regexps and Automata}
@@ -45,62 +43,16 @@
\node (rexp) {\bl{\bf Regexps}};
\node (nfa) [right=of rexp] {\bl{\bf NFAs}};
\node (dfa) [right=of nfa] {\bl{\bf DFAs}};
-\onslide<3->{\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}};}
-\path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa);
-\path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa);
-\onslide<3->{\path[->, red, line width=2mm] (dfa) edge node [below=9mm, black] {minimisation} (mdfa);}
-\onslide<2->{\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp);}
+\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}};
+\path[->,red, line width=2mm] (rexp) edge node [above=4mm, black]
+ {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa);
+\path[->,red, line width=2mm] (nfa) edge node [above=4mm, black]
+ {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa);
+\path[->, red, line width=2mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa);
+\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp);
\end{tikzpicture}\\
\end{center}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}}
-
-\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -108,45 +60,29 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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};
+\frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}}
- %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}
+\begin{tikzpicture}
+\begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,5,...,30},
+ xmax=30,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=10cm,
+ height=7cm,
+ legend entries={Python,Ruby,my NFA},
+ legend pos=north west,
+ legend cell align=left]
+\addplot[blue,mark=*, mark options={fill=white}]
+ table {re-python.data};
+\addplot[brown,mark=pentagon*, mark options={fill=white}]
+ table {re-ruby.data};
+\addplot[red,mark=triangle*, mark options={fill=white}]
+ table {nfasearch.data};
+\end{axis}
\end{tikzpicture}
\end{frame}}
@@ -154,105 +90,42 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}<2>[c]
+\begin{frame}[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$} ()
- ;
+\begin{tikzpicture}[scale=2,>=stealth',very thick,
+ every state/.style={minimum size=0pt,
+ draw=blue!50,very thick,fill=blue!20},]
+ \node[state, initial] (q0) at ( 0,1) {$q_0$};
+ \node[state] (q1) at ( 1,1) {$q_1$};
+ \node[state, accepting] (q2) at ( 2,1) {$q_2$};
+ \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
+ (q1) edge[bend left] node[above] {\alert{$b$}} (q0)
+ (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
+ (q1) edge node[above] {\alert{$a$}} (q2)
+ (q2) edge [loop right] node {\alert{$a$}} ()
+ (q0) edge [loop below] node {\alert{$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$}\\
+\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l}
+\bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b + q_2\,b$} & (start state)\\
\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->{
+\onslide<2->{
Arden's Lemma:
\begin{center}
If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
\end{center}
}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -334,11 +207,11 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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$};
@@ -356,8 +229,43 @@
\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}
+&
+\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);
+
+\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}}
+\end{tabular}
\end{center}
+
\mbox{}\\[-20mm]\mbox{}
\begin{center}
@@ -378,64 +286,297 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}<1-2>[c]
+\begin{frame}[c]
+\frametitle{Alternatives}
+\mbox{}\\[-17mm]\mbox{}
\begin{center}
\begin{tikzpicture}[>=stealth',very thick,auto,
- every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]
-\node[state,initial] (q_0) {$q_0$};
+ 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$};
-\node[state, accepting] (q_4) [right=of q_1] {$q_4$};
+\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 right] node {\alert{$a, b$}} ();
+\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);
+\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);}
+\only<3->{
+\path[<-] (q_0) edge node [above] {\alert{$a$}} (q_1);
+\path[<-] (q_1) edge node [above] {\alert{$a$}} (q_4);
+\path[<-] (q_4) edge [loop above] node {\alert{$a, b$}} ();
+\path[<-] (q_3) edge node [right] {\alert{$a$}} (q_4);
+\path[<-] (q_2) edge node [above] {\alert{$a$}} (q_3);
+\path[<-] (q_1) edge node [right] {\alert{$b$}} (q_2);
+\path[<-] (q_0) edge node [above] {\alert{$b$}} (q_2);
+\path[<-] (q_2) edge [loop left] node {\alert{$b$}} ();
+\path[<-] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);}
\end{tikzpicture}
-\end{center}\pause
+\end{center}
+\mbox{}\\[-18mm]
+
+\begin{itemize}
+\item<2-> exchange initial / accepting states
+\item<3-> reverse all edges
+\item<4-> subset construction $\Rightarrow$ DFA
+\item<5-> repeat once more \onslide<6->{$\Rightarrow$ minimal DFA}
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Regular Languages}
+
+Two equivalent definitions:\bigskip
-\mbox{}\\[-20mm]\mbox{}
+\begin{quote}\rm A language is \alert{regular} iff there exists a
+regular expression that recognises all its strings.
+\end{quote}
+
+\begin{quote}\rm A language is \alert{regular} iff there exists an
+automaton that recognises all its strings.
+\end{quote}\bigskip\bigskip
+
+
+\small
+for example $a^nb^n$ is not regular
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Negation}
+
+Regular languages are closed under negation:\bigskip
\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{tikzpicture}[scale=2,>=stealth',very thick,
+ every state/.style={minimum size=0pt,
+ draw=blue!50,very thick,fill=blue!20}]
+ \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] {\alert{$a$}} (q1)
+ (q1) edge[bend left] node[above] {\alert{$b$}} (q0)
+ (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
+ (q1) edge node[above] {\alert{$a$}} (q2)
+ (q2) edge [loop right] node {\alert{$a$}} ()
+ (q0) edge [loop below] node {\alert{$b$}} ();
+\end{tikzpicture}
+\end{center}\bigskip\bigskip
-\end{frame}}
+\onslide<2>{But requires that the automaton is \alert{completed}!}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\mbox{\lstinputlisting[language=While]{../progs/fib.while}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{??}
+
+\mbox{\lstinputlisting[language=While]{../progs/collatz.while}}
+
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
+\frametitle{A Compiler}
+
+\begin{tikzpicture}[scale=1]
+ \draw[line width=1mm] (-0.3, 0) rectangle (1.5,2);
+ \draw[line width=1mm] (-1.8, 0) rectangle (-3.6,2);
+ \draw (4.4,1) node {Code Gen};
+ \draw (0.6,1.7) node {\small Parser};
+ \draw (-2.7,1.7) node {\small Lexer};
+
+ \draw[red,->,line width = 2mm] (1.7,1) -- (3.2,1);
+ \draw[red,<-,line width = 2mm] (-0.6,1) -- (-1.6,1);
+ \draw[red,<-,line width = 2mm] (-3.8,1) -- (-4.8,1);
+
+ \draw (-4.6,1.7) node {\small string};
+ \draw (-1.1,1.7) node {\small tokens};
+ \draw ( 2.3,1.7) node {\small AST};
+\end{tikzpicture}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+
+\tt
+\begin{center}\large
+\code{"if true then then 42 else +"}
+\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$ {$\sim$(*$\slash$)} $\cdot$ ALL$^*$) $\cdot$ {*$\slash$}
+\end{tabular}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+
+\tt
+\begin{center}\large
+\code{"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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+
+There is one small problem with the tokenizer. How should we
+tokenize:
+
+\begin{center}
+\large\code{"x-3"}
+\end{center}
+
+\tt
+\begin{tabular}{@{}l}
+ID: \ldots\\
+OP:\\
+\hspace{5mm}\texttt{"+"}, \texttt{"-"}\\
+NUM:\\
+\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {''0''}\\
+NUMBER:\\
+\hspace{5mm}NUM + (\texttt{"-"} $\cdot$ NUM)\\
+\end{tabular}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{POSIX: Two Rules}
\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}
+\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}\bigskip\bigskip\pause
+
+\small
+\hfill most posix matchers are buggy\\
+\footnotesize
+\hfill \url{http://www.haskell.org/haskellwiki/Regex_Posix}
+
+%\url{http://www.technologyreview.com/tr10/?year=2011}
+%finite deterministic automata/ nondeterministic automaton
+%\item problem with infix operations, for example i-12
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Sulzmann Matcher}
+
+We want to match the string \bl{$abc$} using \bl{$r_1$}:
-\end{frame}}
+\begin{center}
+\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$}};\pause
+\node (r3) [right=of r2] {\bl{$r_3$}};
+\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};\pause
+\node (r4) [right=of r3] {\bl{$r_4$}};
+\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};\pause
+\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};\pause
+\node (v4) [below=of r4] {\bl{$v_4$}};
+\draw[->,line width=1mm] (r4) -- (v4);\pause
+\node (v3) [left=of v4] {\bl{$v_3$}};
+\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};\pause
+\node (v2) [left=of v3] {\bl{$v_2$}};
+\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};\pause
+\node (v1) [left=of v2] {\bl{$v_1$}};
+\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};\pause
+\draw[->,line width=0.5mm] (r3) -- (v3);
+\draw[->,line width=0.5mm] (r2) -- (v2);
+\draw[->,line width=0.5mm] (r1) -- (v1);
+\end{tikzpicture}
+\end{center}
+
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
\end{document}
%%% Local Variables: