2 \usepackage{beamerthemeplaincu}

     2 \usepackage{../slides}

     3 \usepackage[absolute,overlay]{textpos}

     3 \usepackage{../graphics}

     4 \usepackage{ifthen}

     5 \usepackage{tikz}

     6 \usepackage{pgf}

     7 \usepackage{calc} 

     8 \usepackage{ulem}

     9 \usepackage{courier}

    10 \usepackage{listings}

    11 \renewcommand{\uline}[1]{#1}

    12 \usetikzlibrary{arrows}

    13 \usetikzlibrary{automata}

    14 \usetikzlibrary{shapes}

    15 \usetikzlibrary{shadows}

    16 \usetikzlibrary{positioning}

    17 \usetikzlibrary{calc}

    18 \usetikzlibrary{fit}

    19 \usetikzlibrary{plotmarks}

    20 \usetikzlibrary{backgrounds}

    21 \usepackage{graphicx} 

    25 \makeatletter

     7 \hfuzz=220pt 

    26 \lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}}

     8 

    27 \@empty\z@\@empty

     9 \pgfplotsset{compat=1.11}

    28 \makeatother

    10 

    29 

    11 \newcommand{\bl}[1]{\textcolor{blue}{#1}}  

    30 

    12 

    31 \renewcommand{\slidecaption}{AFL 04, King's College London, 16.~October 2013}

    13 \renewcommand{\slidecaption}{AFL 04, King's College London}

    32 \newcommand{\bl}[1]{\textcolor{blue}{#1}}       

    33 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions

    38 \mode<presentation>{

    18 \begin{frame}[t]

    39 \begin{frame}<1>[t]

    55 

    34 \end{frame}

    56 

    57 \end{frame}}

    82 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    59 

    83 \mode<presentation>{

    60 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    84 \begin{frame}[c]

    85 \frametitle{\begin{tabular}{c}DFAs\end{tabular}}

    86 

    87 A deterministic finite automaton consists of:

    88 

    89 \begin{itemize}

    90 \item a finite set of states, \bl{$Q$}

    91 \item one of these states is the start state, \bl{$q_0$}

    92 \item there is transition function, \bl{$\delta$}, and

    93 \item some states are accepting states, \bl{$F$}

    94 \medskip 

    95 \end{itemize}

    96 

    97 \begin{center}

    98 \bl{$A(Q, q_0, \delta, F)$}

    99 \end{center}

   100 \end{frame}}

   101 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   102 

   103 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   104 \mode<presentation>{

   105 \begin{frame}[c]

   106 \frametitle{\begin{tabular}{c}State Nodes\end{tabular}}

   107 

   108 \hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont

   109 \lstinputlisting{../progs/appA.scala}}}

   110 

   111 \end{frame}}

   112 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   113 

   114 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   115 \mode<presentation>{

   116 \begin{frame}[c]

   117 \frametitle{\begin{tabular}{c}DFAs\;\;\;\end{tabular}}

   118 

   119 \mbox{}\\[7mm]

   120 

   121 \mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont

   122 \lstinputlisting{../progs/appB.scala}}}

   123 

   124 \only<2->{

   125 \begin{textblock}{9}(7.5,0.5)

   126 \begin{tikzpicture}

   127 \draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 

   128 {\normalsize\color{darkgray}

   129 \begin{minipage}{6cm}

   130 \begin{tabular}{l}

   131 \bl{$\hat{\delta}(q, \texttt{""}) \dn q$}\\

   132 \bl{$\hat{\delta}(q, c::s) \dn \hat{\delta}(\delta(q, c), s)$}\\[4mm]

   133 \bl{$\hat{\delta}(q_0, s) \in F$}

   134 \end{tabular}

   135 \end{minipage}};

   136 \end{tikzpicture}

   137 \end{textblock}}

   138 

   139 \end{frame}}

   140 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   141 

   142 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   143 \mode<presentation>{

   145 

    62 \frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}}

   146 \mbox{}\hspace{-10mm}

   147 \begin{tikzpicture}[scale=0.6,>=stealth',very thick,auto,

   148                              every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]

   149 \node[state,initial]  (q_0)  {$q_0$};

   150 \node[state] (q_1) [right=of q_0] {$q_1$};

   151 \node[state] (q_2) [below right=of q_0] {$q_2$};

   152 \node[state] (q_3) [right=of q_2] {$q_3$};

   153 \node[state, accepting] (q_4) [right=of q_1] {$q_4$};

   154 \path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);

   155 \path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);

   156 \path[->] (q_4) edge [loop right] node  {\alert{$a, b$}} ();

   157 \path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);

   158 \path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);

   159 \path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);

   160 \path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);

   161 \path[->] (q_2) edge [loop left] node  {\alert{$b$}} ();

   162 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);

   163 \end{tikzpicture}

   164 

   165 \only<1->{

   166 \begin{textblock}{9}(7.4,3.5)

   167 \begin{tikzpicture}

   168 \draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 

   169 {\normalsize\color{darkgray}

   170 \begin{minipage}{6.6cm}

   171 \hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{8}{10}\selectfont

   172 \lstinputlisting{../progs/appC.scala}}}

   173 \end{minipage}};

   174 \end{tikzpicture}

   175 \end{textblock}}

   176 

   177 \end{frame}}

   178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   179 

   180 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   181 \mode<presentation>{

   182 \begin{frame}[c]

   183 \frametitle{\begin{tabular}{c}NFAs\end{tabular}}

   184 

   185 A non-deterministic finite automaton \bl{$A(Q, q_0, \delta, F)$} consists of:\medskip

   186 

   187 \begin{itemize}

   188 \item a finite set of states, \bl{$Q$}

   189 \item one of these states is the start state, \bl{$q_0$}

   190 \item some states are accepting states, \bl{$F$},

   191 \item there is transition \alert{relation}, \bl{$\delta$}, and

   192 \item there are \alert{silent} transitions\medskip 

   193 \end{itemize}

   194 

   195 

   196 \begin{center}

   197 \begin{tabular}{c}

   198 \bl{$(q_1, a) \rightarrow q_2$}\\

   199 \bl{$(q_1, a) \rightarrow q_3$}\\

   200 \end{tabular}

   201 \hspace{10mm}

   202 \begin{tabular}{c}

   203 \bl{$(q_1, \epsilon) \rightarrow q_2$}\\

   204 \end{tabular}

   205 \end{center}

   206 

   207 \end{frame}}

   208 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   209 

   210 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   211 \mode<presentation>{

   212 \begin{frame}[c]

   213 

   214 \hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont

   215 \lstinputlisting{../progs/appD.scala}}}

   216 

   217 \end{frame}}

   218 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   219 

   220 

   221 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   222 \mode<presentation>{

   223 \begin{frame}[t]

   224 

   225 \mbox{}\hspace{-10mm}

   226 \begin{tikzpicture}[scale=0.6,>=stealth',very thick,auto,

   227                              every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]

   228 \node[state,initial]  (q_0)  {$q_0$};

   229 \node[state] (q_1) [above=of q_0] {$q_1$};

   230 \node[state, accepting] (q_2) [below=of q_0] {$q_2$};

   231 \path[->] (q_0) edge node [left]  {\alert{$\epsilon$}} (q_1);

   232 \path[->] (q_0) edge node [left]  {\alert{$\epsilon$}} (q_2);

   233 \path[->] (q_0) edge [loop right] node  {\alert{$a$}} ();

   234 \path[->] (q_1) edge [loop above] node  {\alert{$a$}} ();

   235 \path[->] (q_2) edge [loop below] node  {\alert{$b$}} ();

   236 \end{tikzpicture}

   237 

   238 \only<1->{

   239 \begin{textblock}{9}(6,1.5)

   240 \begin{tikzpicture}

   241 \draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 

   242 {\normalsize\color{darkgray}

   243 \begin{minipage}{7cm}

   244 \hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{8}{10}\selectfont

   245 \lstinputlisting{../progs/appE.scala}}}

   246 \end{minipage}};

   247 \end{tikzpicture}

   248 \end{textblock}}

   249 

   250 \end{frame}}

   251 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   252 

   253 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   254 \mode<presentation>{

   255 \begin{frame}[c]

   256 \frametitle{Rexp to NFA}

   257 

   258 Thompson's construction of a NFA from a regular expression:

   259 

   260 \begin{center}

   261 \begin{tabular}[t]{l@{\hspace{10mm}}l}

   262 \raisebox{1mm}{\bl{$\varnothing$}} & 

   263 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

   264 \node[state, initial]  (q_0)  {$\mbox{}$};

   265 \end{tikzpicture}\\\\

   266 \raisebox{1mm}{\bl{$\epsilon$}} & 

   267 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

   268 \node[state, initial, accepting]  (q_0)  {$\mbox{}$};

   269 \end{tikzpicture}\\\\

   270 \raisebox{2mm}{\bl{$c$}} & 

   271 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

   272 \node[state, initial]  (q_0)  {$\mbox{}$};

   273 \node[state, accepting]  (q_1)  [right=of q_0] {$\mbox{}$};

   274 \path[->] (q_0) edge node [below]  {\alert{$c$}} (q_1);

   275 \end{tikzpicture}\\\\

   276 \end{tabular}

   277 \end{center}

   278 

   279 \end{frame}}

   280 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   281 

   282 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   283 \mode<presentation>{

   284 \begin{frame}[t]

   285 \frametitle{Case $r_1\cdot r_2$}

   286 

   287 \mbox{}\bigskip

   288 \onslide<1>{By recursion we are given two automata:\bigskip}

   289 

   290 {\centering\begin{tikzpicture}[node distance=3mm,

   291                              >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

   292 \node[state, initial]  (q_0)  {$\mbox{}$};

   293 \node (r_1)  [right=of q_0] {$\ldots$};

   294 \only<1>{

   295 \node[state, accepting]  (t_1)  [right=of r_1] {$\mbox{}$};

   296 \node[state, accepting]  (t_2)  [above=of t_1] {$\mbox{}$};

   297 \node[state, accepting]  (t_3)  [below=of t_1] {$\mbox{}$};}

   298 \only<2>{

   299 \node[state]  (t_1)  [right=of r_1] {$\mbox{}$};

   300 \node[state]  (t_2)  [above=of t_1] {$\mbox{}$};

   301 \node[state]  (t_3)  [below=of t_1] {$\mbox{}$};}

   302 \only<1>{\node[state, initial]  (a_0)  [right=2.5cm of t_1] {$\mbox{}$};}

   303 \only<2>{\node[state]  (a_0)  [right=2.5cm of t_1] {$\mbox{}$};}

   304 \node (b_1)  [right=of a_0] {$\ldots$};

   305 \node[state, accepting]  (c_1)  [right=of b_1] {$\mbox{}$};

   306 \node[state, accepting]  (c_2)  [above=of c_1] {$\mbox{}$};

   307 \node[state, accepting]  (c_3)  [below=of c_1] {$\mbox{}$};

   308 \only<2>{

   309 \path[->] (t_1) edge node [above, pos=0.3]  {\alert{$\epsilon$}} (a_0);

   310 \path[->] (t_2) edge node [above]  {\alert{$\epsilon$}} (a_0);

   311 \path[->] (t_3) edge node [below]  {\alert{$\epsilon$}} (a_0);

   312 }

   313 \begin{pgfonlayer}{background}

   314 \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)] {};}

   315 \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)] {};}

   316 \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)] {};}

   317 \only<1>{\node [yshift=2mm] at (1.north) {\bl{$r_1$}};}

   318 \only<1>{\node [yshift=2mm] at (2.north) {\bl{$r_2$}};}

   319 \only<2>{\node [yshift=2mm] at (3.north) {\bl{$r_1\cdot r_2$}};}

   320 \end{pgfonlayer}

   321 \end{tikzpicture}}\bigskip\bigskip

   322 

   323 \small

   324 We need to (1) change the accepting nodes of the first automaton into non-accepting nodes, and (2) connect them

   325 via $\epsilon$-transitions to the starting state of the second automaton. 

   326 

   327 \end{frame}}

   328 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   329 

   330 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   331 \mode<presentation>{

   332 \begin{frame}[t]

   333 \frametitle{Case $r_1+ r_2$}

   334 

   335 \onslide<1>{By recursion we are given two automata:\smallskip}

   336 

   337 \hspace{2cm}\begin{tikzpicture}[node distance=3mm,

   338                              >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

   339 \onslide<1>{\node at (0,0)  (1)  {$\mbox{}$};}

   340 \onslide<2>{\node at (0,0) [state, initial]  (1)  {$\mbox{}$};}

   341 \only<1>{

   342 \node[state, initial]  (2)  [above right=16mm of 1] {$\mbox{}$};

   343 \node[state, initial]  (3)  [below right=16mm of 1] {$\mbox{}$};}

   344 \only<2>{

   345 \node[state]  (2)  [above right=16mm of 1] {$\mbox{}$};

   346 \node[state]  (3)  [below right=16mm of 1] {$\mbox{}$};}

   347 

   348 \node (a)  [right=of 2] {$\ldots$};

   349 \node[state, accepting]  (a1)  [right=of a] {$\mbox{}$};

   350 \node[state, accepting]  (a2)  [above=of a1] {$\mbox{}$};

   351 \node[state, accepting]  (a3)  [below=of a1] {$\mbox{}$};

   352 

   353 \node (b)  [right=of 3] {$\ldots$};

   354 \node[state, accepting]  (b1)  [right=of b] {$\mbox{}$};

   355 \node[state, accepting]  (b2)  [above=of b1] {$\mbox{}$};

   356 \node[state, accepting]  (b3)  [below=of b1] {$\mbox{}$};

   357 \only<2>{

   358 \path[->] (1) edge node [above]  {\alert{$\epsilon$}} (2);

   359 \path[->] (1) edge node [below]  {\alert{$\epsilon$}} (3);

   360 }

   361 \begin{pgfonlayer}{background}

   362 \only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};}

   363 \only<1>{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (3) (b1) (b2) (b3)] {};}

   364 \only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3) (b2) (b3)] {};}

   365 \only<1>{\node [yshift=3mm] at (1.north) {\bl{$r_1$}};}

   366 \only<1>{\node [yshift=3mm] at (2.north) {\bl{$r_2$}};}

   367 \only<2>{\node [yshift=3mm] at (3.north) {\bl{$r_1+ r_2$}};}

   368 \end{pgfonlayer}

   369 \end{tikzpicture}

   370 

   371 \small

   372 We (1) need to introduce a new starting state and (2) connect it to the original two starting states.

   373 \end{frame}}

   374 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   375 

   376 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   377 \mode<presentation>{

   378 \begin{frame}[c]

   379 \frametitle{Case $r^*$}

   380 

   381 \onslide<1>{By recursion we are given an automaton for $r$:\smallskip}

   382 

   383 \hspace{2cm}\begin{tikzpicture}[node distance=3mm,

   384                              >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

   385 \onslide<1>{\node at (0,0)  (1)  {$\mbox{}$};}

   386 \onslide<2->{\node at (0,0) [state, initial,accepting]  (1)  {$\mbox{}$};}

   387 \only<1>{\node[state, initial]  (2)  [right=16mm of 1] {$\mbox{}$};}

   388 \only<2->{\node[state]  (2)  [right=16mm of 1] {$\mbox{}$};}

   389 \node (a)  [right=of 2] {$\ldots$};

   390 \only<1>{

   391 \node[state, accepting]  (a1)  [right=of a] {$\mbox{}$};

   392 \node[state, accepting]  (a2)  [above=of a1] {$\mbox{}$};

   393 \node[state, accepting]  (a3)  [below=of a1] {$\mbox{}$};}

   394 \only<2->{

   395 \node[state]  (a1)  [right=of a] {$\mbox{}$};

   396 \node[state]  (a2)  [above=of a1] {$\mbox{}$};

   397 \node[state]  (a3)  [below=of a1] {$\mbox{}$};}

   398 \only<2->{

   399 \path[->] (1) edge node [above]  {\alert{$\epsilon$}} (2);

   400 \path[->] (a1) edge [bend left=45] node [above]  {\alert{$\epsilon$}} (1);

   401 \path[->] (a2) edge [bend right] node [below]  {\alert{$\epsilon$}} (1);

   402 \path[->] (a3) edge [bend left=45] node [below]  {\alert{$\epsilon$}} (1);

   403 

   404 }

   405 \begin{pgfonlayer}{background}

   406 \only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};}

   407 \only<2->{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};}

   408 \only<1>{\node [yshift=3mm] at (1.north) {\bl{$r$}};}

   409 \only<2->{\node [yshift=3mm] at (2.north) {\bl{$r^*$}};}

   410 \end{pgfonlayer}

   411 \end{tikzpicture}\bigskip

   412 

   413 \onslide<3->{

   414 Why can't we just have an epsilon transition from the accepting states to the starting state?}

   415 

   416 \end{frame}}

   417 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   418 

   419 

   420 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   421 \mode<presentation>{

   422 \begin{frame}[t]

   423 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}

   465 \end{frame}}

   104 \end{frame}

   466 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   105 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   467 

   106 

   468 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   469 \mode<presentation>{

   470 \begin{frame}[c]

   471 \frametitle{Greedy Depth-First}

   472 

   473 \hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont

   474 \lstinputlisting{../progs/appG.scala}}}

   475 

   476 \end{frame}}

   477 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   637 \item For  all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} tests wether

   266 \item For  all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether

   642 \item Repeat last step until no chance.

   271 \item Repeat last step until no change.

   650 \mode<presentation>{

   279 \begin{frame}[c]

   651 \begin{frame}<1-2>[c]

   676 \begin{tikzpicture}[>=stealth',very thick,auto,

   304 \begin{tikzpicture}[scale=0.8,line width=0.8mm]

   677                              every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]

   305 \draw (0,0) -- (4,0);

   678 \node[state,initial]  (q_02)  {$q_{0, 2}$};

   306 \draw (0,1) -- (4,1);

   679 \node[state] (q_13) [right=of q_02] {$q_{1, 3}$};

   307 \draw (0,2) -- (3,2);

   680 \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$};

   308 \draw (0,3) -- (2,3);

   681 \path[->] (q_02) edge [bend left] node [above]  {\alert{$a$}} (q_13);

   309 \draw (0,4) -- (1,4);

   682 \path[->] (q_13) edge [bend left] node [below]  {\alert{$b$}} (q_02);

   310 

   683 \path[->] (q_02) edge [loop below] node  {\alert{$b$}} ();

   311 \draw (0,0) -- (0, 4);

   684 \path[->] (q_13) edge node [above]  {\alert{$a$}} (q_4);

   312 \draw (1,0) -- (1, 4);

   685 \path[->] (q_4) edge [loop above] node  {\alert{$a, b$}} ();

   313 \draw (2,0) -- (2, 3);

   686 \end{tikzpicture}\\

   314 \draw (3,0) -- (3, 2);

   687 minimal automaton

   315 \draw (4,0) -- (4, 1);

   688 \end{center}

   316 

   689 

   317 \draw (0.5,-0.5) node {$q_0$}; 

   690 \end{frame}}

   318 \draw (1.5,-0.5) node {$q_1$}; 

   691 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   319 \draw (2.5,-0.5) node {$q_2$}; 

   692 

   320 \draw (3.5,-0.5) node {$q_3$};

   693 

   321  

   694 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   322 \draw (-0.5, 3.5) node {$q_1$}; 

   695 \mode<presentation>{

   323 \draw (-0.5, 2.5) node {$q_2$}; 

   696 \begin{frame}<1-2>[c]

   324 \draw (-0.5, 1.5) node {$q_3$}; 

   325 \draw (-0.5, 0.5) node {$q_4$}; 

   326 

   327 \draw (0.5,0.5) node {\large$\star$}; 

   328 \draw (1.5,0.5) node {\large$\star$}; 

   329 \draw (2.5,0.5) node {\large$\star$}; 

   330 \draw (3.5,0.5) node {\large$\star$};

   331 \end{tikzpicture}

   332 \end{center}

   333 

   334 \end{frame}

   335 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   336 

   337 

   338 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   339 \begin{frame}[c]

   716 \end{center}\pause

   359 \end{center}