288 |
288 |
289 \end{frame} |
289 \end{frame} |
290 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
290 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
291 |
291 |
292 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
292 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
293 \begin{frame}[c] |
293 \begin{frame}[t] |
294 \frametitle{Automata} |
294 \frametitle{Automata} |
295 |
295 |
296 A \alert{\bf deterministic finite automaton}, DFA, consists of: |
296 A \alert{\bf deterministic finite automaton}, DFA, consists of: |
297 |
297 |
298 \begin{itemize} |
298 \begin{itemize} |
299 \item an alphabet \bl{$\varSigma$} |
299 \item an alphabet \bl{$\varSigma$} |
300 \item a set of states \bl{$Q$} |
300 \item a set of states \bl{$\mbox{Q}$} |
301 \item one of these states is the start state \bl{$\mbox{Q}_0$} |
301 \item one of these states is the start state \bl{$\mbox{Q}_0$} |
302 \item some states are accepting states \bl{$F$}, and |
302 \item some states are accepting states \bl{$F$}, and |
303 \item there is transition function \bl{$\delta$}\bigskip |
303 \item there is transition function \bl{$\delta$}\bigskip |
304 |
304 |
305 \small |
305 \small |
318 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
318 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
319 \begin{frame}[c] |
319 \begin{frame}[c] |
320 |
320 |
321 \begin{center} |
321 \begin{center} |
322 \begin{tikzpicture}[>=stealth',very thick,auto, |
322 \begin{tikzpicture}[>=stealth',very thick,auto, |
323 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
323 every state/.style={minimum size=0pt,inner sep=2pt, |
|
324 draw=blue!50,very thick,fill=blue!20},] |
324 \node[state,initial] (Q_0) {$\mbox{Q}_0$}; |
325 \node[state,initial] (Q_0) {$\mbox{Q}_0$}; |
325 \node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$}; |
326 \node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$}; |
326 \node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$}; |
327 \node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$}; |
327 \node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$}; |
328 \node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$}; |
328 \node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$}; |
329 \node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$}; |
336 \path[->] (Q_2) edge [loop left] node {\alert{$b$}} (); |
337 \path[->] (Q_2) edge [loop left] node {\alert{$b$}} (); |
337 \path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (Q_0); |
338 \path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (Q_0); |
338 \end{tikzpicture} |
339 \end{tikzpicture} |
339 \end{center} |
340 \end{center} |
340 |
341 |
341 |
342 \mbox{}\\[-14mm] |
|
343 \only<1>{ |
342 \begin{itemize} |
344 \begin{itemize} |
343 \item the start state can be an accepting state |
345 \item the start state can be an accepting state |
344 \item it is possible that there is no accepting state |
346 \item it is possible that there is no accepting state |
345 \item all states might be accepting (but this does not necessarily mean all strings are accepted) |
347 \item all states might be accepting (but this does not necessarily mean all strings are accepted) |
346 \end{itemize} |
348 \end{itemize}} |
347 |
349 \only<2>{ |
348 \end{frame} |
|
349 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
350 |
|
351 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
352 \begin{frame}[c] |
|
353 |
|
354 \begin{center} |
|
355 \begin{tikzpicture}[>=stealth',very thick,auto, |
|
356 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
|
357 \node[state,initial] (Q_0) {$\mbox{Q}_0$}; |
|
358 \node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$}; |
|
359 \node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$}; |
|
360 \node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$}; |
|
361 \node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$}; |
|
362 \path[->] (Q_0) edge node [above] {\alert{$a$}} (Q_1); |
|
363 \path[->] (Q_1) edge node [above] {\alert{$a$}} (Q_4); |
|
364 \path[->] (Q_4) edge [loop right] node {\alert{$a, b$}} (); |
|
365 \path[->] (Q_3) edge node [right] {\alert{$a$}} (Q_4); |
|
366 \path[->] (Q_2) edge node [above] {\alert{$a$}} (Q_3); |
|
367 \path[->] (Q_1) edge node [right] {\alert{$b$}} (Q_2); |
|
368 \path[->] (Q_0) edge node [above] {\alert{$b$}} (Q_2); |
|
369 \path[->] (Q_2) edge [loop left] node {\alert{$b$}} (); |
|
370 \path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (Q_0); |
|
371 \end{tikzpicture} |
|
372 \end{center} |
|
373 |
|
374 for this automaton \bl{$\delta$} is the function\\ |
350 for this automaton \bl{$\delta$} is the function\\ |
375 |
351 |
376 \begin{center} |
352 \begin{center} |
377 \begin{tabular}{lll} |
353 \begin{tabular}{lll} |
378 \bl{$(\mbox{Q}_0, a) \rightarrow \mbox{Q}_1$} & \bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_4$} |
354 \bl{$(\mbox{Q}_0, a) \rightarrow \mbox{Q}_1$} & \bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_4$} |
379 & \bl{$(\mbox{Q}_4, a) \rightarrow \mbox{Q}_4$}\\ |
355 & \bl{$(\mbox{Q}_4, a) \rightarrow \mbox{Q}_4$}\\ |
380 \bl{$(\mbox{Q}_0, b) \rightarrow \mbox{Q}_2$} & \bl{$(\mbox{Q}_1, b) \rightarrow \mbox{Q}_2$} & |
356 \bl{$(\mbox{Q}_0, b) \rightarrow \mbox{Q}_2$} & \bl{$(\mbox{Q}_1, b) \rightarrow \mbox{Q}_2$} & |
381 \bl{$(\mbox{Q}_4, b) \rightarrow \mbox{Q}_4$}\\ |
357 \bl{$(\mbox{Q}_4, b) \rightarrow \mbox{Q}_4$}\\ |
382 \end{tabular}\ldots |
358 \end{tabular}\ldots |
383 \end{center} |
359 \end{center} |
384 |
360 } |
385 \end{frame} |
361 |
386 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
362 \end{frame} |
|
363 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
364 |
387 |
365 |
388 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
366 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
389 \begin{frame}[t] |
367 \begin{frame}[t] |
390 \frametitle{Accepting a String} |
368 \frametitle{Accepting a String} |
391 |
369 |
1067 |
1045 |
1068 |
1046 |
1069 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1047 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1070 \begin{frame}[c] |
1048 \begin{frame}[c] |
1071 \frametitle{Alternatives} |
1049 \frametitle{Alternatives} |
1072 \mbox{}\\[-17mm]\mbox{} |
1050 \mbox{}\\[-14mm]\mbox{} |
1073 |
1051 |
1074 \begin{center} |
1052 \begin{center} |
1075 \begin{tikzpicture}[>=stealth',very thick,auto, |
1053 \begin{tikzpicture}[>=stealth',very thick,auto, |
1076 every state/.style={minimum size=0pt, |
1054 every state/.style={minimum size=0pt, |
1077 inner sep=2pt,draw=blue!50,very thick,fill=blue!20}] |
1055 inner sep=2pt,draw=blue!50,very thick,fill=blue!20}] |
1106 \end{center} |
1084 \end{center} |
1107 \mbox{}\\[-18mm] |
1085 \mbox{}\\[-18mm] |
1108 |
1086 |
1109 \small |
1087 \small |
1110 \begin{itemize} |
1088 \begin{itemize} |
1111 \item<2-> exchange initial / accepting states\\[-2mm] |
1089 \item<1-> exchange initial / accepting states\\[-2mm] |
1112 \item<3-> reverse all edges\\[-2mm] |
1090 \item<2-> reverse all edges\\[-2mm] |
1113 \item<4-> subset construction $\Rightarrow$ DFA\\[-2mm] |
1091 \item<3-> subset construction $\Rightarrow$ DFA\\[-2mm] |
1114 \item<5-> remove dead states\\[-2mm] |
1092 \item<4-> remove dead states\\[-2mm] |
1115 \item<6-> repeat once more |
1093 \item<5-> repeat once more |
1116 \onslide<6->{$\Rightarrow$ minimal DFA} |
1094 \onslide<6->{$\Rightarrow$ minimal DFA} |
1117 \end{itemize} |
1095 \end{itemize} |
1118 |
1096 |
1119 \end{frame} |
1097 \end{frame} |
1120 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1098 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |