101 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
101 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
102 |
102 |
103 |
103 |
104 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
104 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
105 \mode<presentation>{ |
105 \mode<presentation>{ |
|
106 \begin{frame}[c] |
|
107 \frametitle{Regexps and Automata} |
|
108 |
|
109 \begin{center} |
|
110 \begin{tikzpicture} |
|
111 \node (rexp) {\bl{\bf Regexps}}; |
|
112 \node (nfa) [right=of rexp] {\bl{\bf NFAs}}; |
|
113 \node (dfa) [right=of nfa] {\bl{\bf DFAs}}; |
|
114 \onslide<3->{\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}};} |
|
115 \path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa); |
|
116 \path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa); |
|
117 \onslide<3->{\path[->, red, line width=2mm] (dfa) edge node [below=9mm, black] {minimisation} (mdfa);} |
|
118 \onslide<2->{\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp);} |
|
119 \end{tikzpicture}\\ |
|
120 \end{center} |
|
121 |
|
122 \end{frame}} |
|
123 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
124 |
|
125 |
|
126 |
|
127 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
128 \mode<presentation>{ |
106 \begin{frame}<1-2>[c] |
129 \begin{frame}<1-2>[c] |
107 |
130 |
108 \begin{center} |
131 \begin{center} |
109 \begin{tikzpicture}[>=stealth',very thick,auto, |
132 \begin{tikzpicture}[>=stealth',very thick,auto, |
110 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
133 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |