49 \item short survey at KEATS; to be answered until Sunday |
65 \item short survey at KEATS; to be answered until Sunday |
50 \end{itemize} |
66 \end{itemize} |
51 |
67 |
52 \end{frame} |
68 \end{frame} |
53 %%%%%%%%%%% |
69 %%%%%%%%%%% |
54 |
|
55 |
|
56 |
|
57 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
58 \begin{frame}[c] |
|
59 \frametitle{Last Week} |
|
60 |
|
61 Last week I showed you a regular expression matcher |
|
62 that works provably correct in all cases (we only |
|
63 started with the proving part though) |
|
64 |
|
65 \begin{center} |
|
66 \bl{$matches\,s\,r$} \;\;if and only if \;\; \bl{$s \in L(r)$} |
|
67 \end{center}\bigskip\bigskip |
|
68 |
|
69 \small |
|
70 \textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)} |
|
71 |
|
72 \end{frame} |
|
73 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
74 |
|
75 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
76 \begin{frame}[c] |
|
77 \frametitle{The Derivative of a Rexp} |
|
78 |
|
79 \begin{center} |
|
80 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
|
81 \bl{$der\, c\, (\ZERO)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\ |
|
82 \bl{$der\, c\, (\ONE)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\ |
|
83 \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\ |
|
84 \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\ |
|
85 \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ |
|
86 & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ |
|
87 & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\ |
|
88 \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\ |
|
89 |
|
90 \bl{$\textit{ders}\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ |
|
91 \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\ |
|
92 \end{tabular} |
|
93 \end{center} |
|
94 |
|
95 \end{frame} |
|
96 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
97 |
|
98 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
99 \begin{frame}[c] |
|
100 \frametitle{Example} |
|
101 |
|
102 Given \bl{$r \dn ((a \cdot b) + b)^*$} what is |
|
103 |
|
104 \begin{center} |
|
105 \def\arraystretch{1.5} |
|
106 \begin{tabular}{@{}lcl} |
|
107 \bl{$\der\,a\,((a \cdot b) + b)^*$} |
|
108 & \bl{$\Rightarrow$}& \bl{$\der\,a\, \underline{((a \cdot b) + b)^*}$}\\ |
|
109 & \bl{$=$} & \bl{$(der\,a\,(\underline{(a \cdot b) + b})) \cdot r$}\\ |
|
110 & \bl{$=$} & \bl{$((der\,a\,(\underline{a \cdot b})) + (der\,a\,b)) \cdot r$}\\ |
|
111 & \bl{$=$} & \bl{$(((der\,a\,\underline{a}) \cdot b) + (der\,a\,b)) \cdot r$}\\ |
|
112 & \bl{$=$} & \bl{$((\ONE \cdot b) + (der\,a\,\underline{b})) \cdot r$}\\ |
|
113 & \bl{$=$} & \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}\\ |
|
114 \end{tabular} |
|
115 \end{center} |
|
116 |
|
117 \end{frame} |
|
118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
119 |
|
120 |
|
121 |
|
122 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
123 \begin{frame}[c] |
|
124 |
|
125 Input: string \bl{$abc$} and regular expression \bl{$r$} |
|
126 |
|
127 \begin{enumerate} |
|
128 \item \bl{$der\,a\,r$} |
|
129 \item \bl{$der\,b\,(der\,a\,r)$} |
|
130 \item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause |
|
131 \item finally check whether the last regular expression can match the empty string |
|
132 \end{enumerate} |
|
133 |
|
134 \end{frame} |
|
135 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
136 |
|
137 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
138 \begin{frame}[t] |
|
139 \frametitle{Simplification} |
|
140 |
|
141 Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows |
|
142 |
|
143 \begin{center} |
|
144 \def\arraystretch{2} |
|
145 \begin{tabular}{@{}lcl} |
|
146 \bl{$((\ONE \cdot b) + \ZERO) \cdot r$} |
|
147 & \bl{$\Rightarrow$} & \bl{$((\underline{\ONE \cdot b}) + \ZERO) \cdot r$}\\ |
|
148 & \bl{$=$} & \bl{$(\underline{b + \ZERO}) \cdot r$}\\ |
|
149 & \bl{$=$} & \bl{$b \cdot r$}\\ |
|
150 \end{tabular} |
|
151 \end{center} |
|
152 |
|
153 \end{frame} |
|
154 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
155 |
|
156 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
157 \begin{frame}[c] |
|
158 \frametitle{Proofs about Rexp} |
|
159 |
|
160 \begin{itemize} |
|
161 \item \bl{$P$} holds for \bl{$\ZERO$}, \bl{$\ONE$} and \bl{c}\bigskip |
|
162 \item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already |
|
163 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip |
|
164 \item \bl{$P$} holds for \bl{$r_1 \cdot r_2$} under the assumption that \bl{$P$} already |
|
165 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip |
|
166 \item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already |
|
167 holds for \bl{$r$}. |
|
168 \end{itemize} |
|
169 |
|
170 \end{frame} |
|
171 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
172 |
|
173 |
|
174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
175 \begin{frame}[c] |
|
176 |
|
177 We proved |
|
178 |
|
179 \begin{center} |
|
180 \bl{$nullable(r)$} \;if and only if\; \bl{$[] \in L(r)$} |
|
181 \end{center} |
|
182 |
|
183 by induction on the regular expression \bl{$r$}.\bigskip\pause |
|
184 |
|
185 \begin{center} |
|
186 {\huge\bf\alert{Any Questions?}} |
|
187 \end{center} |
|
188 |
|
189 \end{frame} |
|
190 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
191 |
|
192 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
193 \begin{frame}[c] |
|
194 \frametitle{\begin{tabular}{c}Proofs about Natural\\[-1mm] Numbers and Strings\end{tabular}} |
|
195 |
|
196 \begin{itemize} |
|
197 \item \bl{$P$} holds for \bl{$0$} and |
|
198 \item \bl{$P$} holds for \bl{$n + 1$} under the assumption that \bl{$P$} already |
|
199 holds for \bl{$n$} |
|
200 \end{itemize}\bigskip |
|
201 |
|
202 \begin{itemize} |
|
203 \item \bl{$P$} holds for \bl{$[]$} and |
|
204 \item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already |
|
205 holds for \bl{$s$} |
|
206 \end{itemize} |
|
207 |
|
208 \end{frame} |
|
209 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
210 |
|
211 |
|
212 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
213 \begin{frame}[c] |
|
214 \frametitle{Correctness Proof \\[-1mm] |
|
215 for our Matcher} |
|
216 |
|
217 \begin{itemize} |
|
218 \item We started from |
|
219 |
|
220 \begin{center} |
|
221 \begin{tabular}{rp{4cm}} |
|
222 & \bl{$s \in L(r)$}\medskip\\ |
|
223 \bl{$\Leftrightarrow$} & \bl{$[] \in \Ders\,s\,(L(r))$}\pause |
|
224 \end{tabular} |
|
225 \end{center}\bigskip |
|
226 |
|
227 \item \textbf{\alert{if}} we can show \bl{$\Ders\, s\,(L(r)) = L(\ders\,s\,r)$} we |
|
228 have\bigskip |
|
229 |
|
230 \begin{center} |
|
231 \begin{tabular}{rp{4cm}} |
|
232 \bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\ |
|
233 \bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\ |
|
234 \bl{$\dn$} & \bl{$matches\,s\,r$} |
|
235 \end{tabular} |
|
236 \end{center} |
|
237 |
|
238 \end{itemize} |
|
239 |
|
240 \end{frame} |
|
241 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
242 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
243 \begin{frame}[c] |
|
244 |
|
245 We need to prove |
|
246 |
|
247 \begin{center} |
|
248 \bl{$L(der\,c\,r) = Der\,c\,(L(r))$} |
|
249 \end{center} |
|
250 |
|
251 also by induction on the regular expression \bl{$r$}. |
|
252 \end{frame} |
|
253 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
254 |
70 |
255 |
71 |
256 |
72 |
257 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
73 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
258 \begin{frame}[t] |
74 \begin{frame}[t] |
1327 |
1143 |
1328 \end{frame} |
1144 \end{frame} |
1329 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1145 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1330 |
1146 |
1331 |
1147 |
|
1148 |
|
1149 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1150 \begin{frame}[c] |
|
1151 |
|
1152 \begin{center} |
|
1153 \begin{tikzpicture}[scale=2,>=stealth',very thick, |
|
1154 every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] |
|
1155 \only<-7>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};} |
|
1156 \only<8->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};} |
|
1157 \only<-7>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};} |
|
1158 \only<8->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};} |
|
1159 \node[state] (q2) at ( 2,1) {$\mbox{Q}_2$}; |
|
1160 \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) |
|
1161 (q1) edge[bend left] node[above] {\alert{$b$}} (q0) |
|
1162 (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) |
|
1163 (q1) edge node[above] {\alert{$a$}} (q2) |
|
1164 (q2) edge [loop right] node {\alert{$a$}} () |
|
1165 (q0) edge [loop below] node {\alert{$b$}} () |
|
1166 ; |
|
1167 \end{tikzpicture} |
|
1168 \end{center}\bigskip |
|
1169 |
|
1170 \begin{center} |
|
1171 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
|
1172 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b + \mbox{Q}_2\,b$}\\ |
|
1173 \bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\ |
|
1174 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\ |
|
1175 \end{tabular} |
|
1176 \end{center} |
|
1177 |
|
1178 |
|
1179 Arden's Lemma: |
|
1180 \begin{center} |
|
1181 If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} |
|
1182 \end{center} |
|
1183 |
|
1184 \only<2-6>{\small |
|
1185 \begin{textblock}{6}(1,0.8) |
|
1186 \begin{bubble}[6.7cm] |
|
1187 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
1188 \multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} \& \bl{$\mbox{Q}_2$}:}\\ |
|
1189 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b + \mbox{Q}_2\,b$}\\ |
|
1190 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} |
|
1191 \end{tabular} |
|
1192 \end{bubble} |
|
1193 \end{textblock}} |
|
1194 |
|
1195 \only<3-6>{\small |
|
1196 \begin{textblock}{6}(2,4.15) |
|
1197 \begin{bubble}[6.7cm] |
|
1198 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
1199 \multicolumn{3}{@{}l}{simplifying \bl{$\mbox{Q}_0$}:}\\ |
|
1200 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\ |
|
1201 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} |
|
1202 \end{tabular} |
|
1203 \end{bubble} |
|
1204 \end{textblock}} |
|
1205 |
|
1206 \only<4-6>{\small |
|
1207 \begin{textblock}{6}(3,7.55) |
|
1208 \begin{bubble}[6.7cm] |
|
1209 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
1210 \multicolumn{3}{@{}l}{Arden for \bl{$\mbox{Q}_2$}:}\\ |
|
1211 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\ |
|
1212 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$} |
|
1213 \end{tabular} |
|
1214 \end{bubble} |
|
1215 \end{textblock}} |
|
1216 |
|
1217 \only<5-6>{\small |
|
1218 \begin{textblock}{6}(4,10.9) |
|
1219 \begin{bubble}[7.5cm] |
|
1220 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
1221 \multicolumn{3}{@{}l}{Substitute \bl{$\mbox{Q}_2$} and simplify:}\\ |
|
1222 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b)$}\\ |
|
1223 \end{tabular} |
|
1224 \end{bubble} |
|
1225 \end{textblock}} |
|
1226 |
|
1227 \only<6>{\small |
|
1228 \begin{textblock}{6}(5,13.4) |
|
1229 \begin{bubble}[7.5cm] |
|
1230 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
1231 \multicolumn{3}{@{}l}{Arden again for \bl{$\mbox{Q}_0$}:}\\ |
|
1232 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\ |
|
1233 \end{tabular} |
|
1234 \end{bubble} |
|
1235 \end{textblock}} |
|
1236 |
|
1237 |
|
1238 \only<7->{\small |
|
1239 \begin{textblock}{6}(6,11.5) |
|
1240 \begin{bubble}[6.7cm] |
|
1241 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
1242 \multicolumn{3}{@{}l}{Finally:}\\ |
|
1243 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\ |
|
1244 \bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a$}\\ |
|
1245 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a^*)$}\\ |
|
1246 \end{tabular} |
|
1247 \end{bubble} |
|
1248 \end{textblock}} |
|
1249 |
|
1250 \end{frame} |
|
1251 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1252 |
|
1253 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1254 \begin{frame}[c] |
|
1255 \frametitle{Regexps and Automata} |
|
1256 |
|
1257 \begin{center} |
|
1258 \begin{tikzpicture} |
|
1259 \node (rexp) {\bl{\bf Regexps}}; |
|
1260 \node (nfa) [right=of rexp] {\bl{\bf NFAs}}; |
|
1261 \node (dfa) [right=of nfa] {\bl{\bf DFAs}}; |
|
1262 \node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}}; |
|
1263 \path[->,red, line width=2mm] (rexp) edge node [above=4mm, black] |
|
1264 {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa); |
|
1265 \path[->,red, line width=2mm] (nfa) edge node [above=4mm, black] |
|
1266 {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa); |
|
1267 \path[->, red, line width=2mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa); |
|
1268 %%\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp); |
|
1269 \path[->, red, line width=2mm] (dfa) edge [bend left=45] node [below, black] {\begin{tabular}{l}Brzozowski's\\ method\end{tabular}} (rexp); |
|
1270 |
|
1271 \end{tikzpicture}\\ |
|
1272 \end{center} |
|
1273 |
|
1274 \end{frame} |
|
1275 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1276 |
|
1277 |
|
1278 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1279 \begin{frame}[t] |
|
1280 \frametitle{\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}} |
|
1281 |
|
1282 \begin{tikzpicture} |
|
1283 \begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs}, |
|
1284 enlargelimits=false, |
|
1285 xtick={0,5,...,30}, |
|
1286 xmax=30, |
|
1287 ymax=35, |
|
1288 ytick={0,5,...,30}, |
|
1289 scaled ticks=false, |
|
1290 axis lines=left, |
|
1291 width=10cm, |
|
1292 height=7cm, |
|
1293 legend entries={Python,Ruby,my NFA}, |
|
1294 legend pos=north west, |
|
1295 legend cell align=left] |
|
1296 \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; |
|
1297 \addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; |
|
1298 \addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data}; |
|
1299 \end{axis} |
|
1300 \end{tikzpicture} |
|
1301 |
|
1302 The punchline is that many existing libraries do depth-first search |
|
1303 in NFAs (backtracking). |
|
1304 |
|
1305 \end{frame} |
|
1306 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1307 |
|
1308 |
|
1309 |
|
1310 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1311 % \begin{frame}[c] |
|
1312 % \frametitle{DFA to Rexp} |
|
1313 |
|
1314 % \begin{center} |
|
1315 % \begin{tikzpicture}[scale=2,>=stealth',very thick, |
|
1316 % every state/.style={minimum size=0pt, |
|
1317 % draw=blue!50,very thick,fill=blue!20},] |
|
1318 % \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
|
1319 % \node[state] (q1) at ( 1,1) {$q_1$}; |
|
1320 % \node[state, accepting] (q2) at ( 2,1) {$q_2$}; |
|
1321 % \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) |
|
1322 % (q1) edge[bend left] node[above] {\alert{$b$}} (q0) |
|
1323 % (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) |
|
1324 % (q1) edge node[above] {\alert{$a$}} (q2) |
|
1325 % (q2) edge [loop right] node {\alert{$a$}} () |
|
1326 % (q0) edge [loop below] node {\alert{$b$}} (); |
|
1327 % \end{tikzpicture} |
|
1328 % \end{center}\bigskip |
|
1329 |
|
1330 % \begin{center} |
|
1331 % \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l} |
|
1332 % \bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b + q_2\,b$} & (start state)\\ |
|
1333 % \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ |
|
1334 % \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ |
|
1335 |
|
1336 % \end{tabular} |
|
1337 % \end{center} |
|
1338 |
|
1339 % Arden's Lemma: |
|
1340 % \begin{center} |
|
1341 % If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} |
|
1342 % \end{center} |
|
1343 |
|
1344 |
|
1345 % \end{frame} |
|
1346 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1347 |
|
1348 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1349 % \begin{frame}[c] |
|
1350 % \frametitle{DFA Minimisation} |
|
1351 |
|
1352 % \begin{enumerate} |
|
1353 % \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$} |
|
1354 % \item Mark all pairs that accepting and non-accepting states |
|
1355 % \item For all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether |
|
1356 % \begin{center} |
|
1357 % \bl{$(\delta(q, c), \delta(p,c))$} |
|
1358 % \end{center} |
|
1359 % are marked. If yes, then also mark \bl{$(q, p)$}. |
|
1360 % \item Repeat last step until no change. |
|
1361 % \item All unmarked pairs can be merged. |
|
1362 % \end{enumerate} |
|
1363 |
|
1364 % \end{frame} |
|
1365 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1366 |
|
1367 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1368 % \begin{frame}[c] |
|
1369 |
|
1370 % \begin{center} |
|
1371 % \begin{tabular}{@{\hspace{-8mm}}cc@{}} |
|
1372 % \begin{tikzpicture}[>=stealth',very thick,auto, |
|
1373 % every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
|
1374 % \node[state,initial] (q_0) {$q_0$}; |
|
1375 % \node[state] (q_1) [right=of q_0] {$q_1$}; |
|
1376 % \node[state] (q_2) [below right=of q_0] {$q_2$}; |
|
1377 % \node[state] (q_3) [right=of q_2] {$q_3$}; |
|
1378 % \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; |
|
1379 % \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); |
|
1380 % \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); |
|
1381 % \path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); |
|
1382 % \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); |
|
1383 % \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); |
|
1384 % \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
|
1385 % \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
|
1386 % \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
|
1387 % \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); |
|
1388 % \end{tikzpicture} |
|
1389 % & |
|
1390 % \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm] |
|
1391 % \draw (0,0) -- (4,0); |
|
1392 % \draw (0,1) -- (4,1); |
|
1393 % \draw (0,2) -- (3,2); |
|
1394 % \draw (0,3) -- (2,3); |
|
1395 % \draw (0,4) -- (1,4); |
|
1396 |
|
1397 % \draw (0,0) -- (0, 4); |
|
1398 % \draw (1,0) -- (1, 4); |
|
1399 % \draw (2,0) -- (2, 3); |
|
1400 % \draw (3,0) -- (3, 2); |
|
1401 % \draw (4,0) -- (4, 1); |
|
1402 |
|
1403 % \draw (0.5,-0.5) node {$q_0$}; |
|
1404 % \draw (1.5,-0.5) node {$q_1$}; |
|
1405 % \draw (2.5,-0.5) node {$q_2$}; |
|
1406 % \draw (3.5,-0.5) node {$q_3$}; |
|
1407 |
|
1408 % \draw (-0.5, 3.5) node {$q_1$}; |
|
1409 % \draw (-0.5, 2.5) node {$q_2$}; |
|
1410 % \draw (-0.5, 1.5) node {$q_3$}; |
|
1411 % \draw (-0.5, 0.5) node {$q_4$}; |
|
1412 |
|
1413 % \draw (0.5,0.5) node {\large$\star$}; |
|
1414 % \draw (1.5,0.5) node {\large$\star$}; |
|
1415 % \draw (2.5,0.5) node {\large$\star$}; |
|
1416 % \draw (3.5,0.5) node {\large$\star$}; |
|
1417 % \draw (0.5,1.5) node {\large$\star$}; |
|
1418 % \draw (2.5,1.5) node {\large$\star$}; |
|
1419 % \draw (0.5,3.5) node {\large$\star$}; |
|
1420 % \draw (1.5,2.5) node {\large$\star$}; |
|
1421 % \end{tikzpicture}} |
|
1422 % \end{tabular} |
|
1423 % \end{center} |
|
1424 |
|
1425 |
|
1426 % \mbox{}\\[-20mm]\mbox{} |
|
1427 |
|
1428 % \begin{center} |
|
1429 % \begin{tikzpicture}[>=stealth',very thick,auto, |
|
1430 % every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
|
1431 % \node[state,initial] (q_02) {$q_{0, 2}$}; |
|
1432 % \node[state] (q_13) [right=of q_02] {$q_{1, 3}$}; |
|
1433 % \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$}; |
|
1434 % \path[->] (q_02) edge [bend left] node [above] {\alert{$a$}} (q_13); |
|
1435 % \path[->] (q_13) edge [bend left] node [below] {\alert{$b$}} (q_02); |
|
1436 % \path[->] (q_02) edge [loop below] node {\alert{$b$}} (); |
|
1437 % \path[->] (q_13) edge node [above] {\alert{$a$}} (q_4); |
|
1438 % \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); |
|
1439 % \end{tikzpicture}\\ |
|
1440 % minimal automaton |
|
1441 % \end{center} |
|
1442 |
|
1443 % \end{frame} |
|
1444 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1445 |
|
1446 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1447 \begin{frame}[c] |
|
1448 \frametitle{Regular Languages} |
|
1449 |
|
1450 Two equivalent definitions:\bigskip |
|
1451 |
|
1452 \begin{quote}\rm A language is \alert{regular} iff there exists a |
|
1453 regular expression that recognises all its strings. |
|
1454 \end{quote} |
|
1455 |
|
1456 \begin{quote}\rm A language is \alert{regular} iff there exists an |
|
1457 automaton that recognises all its strings. |
|
1458 \end{quote}\bigskip\bigskip |
|
1459 |
|
1460 |
|
1461 \small |
|
1462 for example \bl{$a^nb^n$} is not regular |
|
1463 \end{frame} |
|
1464 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1465 |
|
1466 |
|
1467 |
|
1468 |
|
1469 |
|
1470 |
|
1471 |
|
1472 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1473 \begin{frame}[c] |
|
1474 \frametitle{Negation} |
|
1475 |
|
1476 Regular languages are closed under negation:\bigskip |
|
1477 |
|
1478 \begin{center} |
|
1479 \begin{tikzpicture}[scale=2,>=stealth',very thick, |
|
1480 every state/.style={minimum size=0pt, |
|
1481 draw=blue!50,very thick,fill=blue!20}] |
|
1482 \only<1>{\node[state,initial] (q0) at ( 0,1) {$q_0$};} |
|
1483 \only<2>{\node[state,initial,accepting] (q0) at ( 0,1) {$q_0$};} |
|
1484 \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
1485 \only<2>{\node[state,accepting] (q1) at ( 1,1) {$q_1$};} |
|
1486 \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};} |
|
1487 \only<2>{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
1488 \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) |
|
1489 (q1) edge[bend left] node[above] {\alert{$b$}} (q0) |
|
1490 (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) |
|
1491 (q1) edge node[above] {\alert{$a$}} (q2) |
|
1492 (q2) edge [loop right] node {\alert{$a$}} () |
|
1493 (q0) edge [loop below] node {\alert{$b$}} (); |
|
1494 \end{tikzpicture} |
|
1495 \end{center}\bigskip\bigskip |
|
1496 |
|
1497 But requires that the automaton is \alert{completed}! |
|
1498 |
|
1499 \end{frame} |
|
1500 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1501 |
1332 \end{document} |
1502 \end{document} |
1333 |
1503 |
1334 %%% Local Variables: |
1504 %%% Local Variables: |
1335 %%% mode: latex |
1505 %%% mode: latex |
1336 %%% TeX-master: t |
1506 %%% TeX-master: t |