221 \end{frame} |
221 \end{frame} |
222 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
222 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
223 |
223 |
224 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
224 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
225 \begin{frame}[c] |
225 \begin{frame}[c] |
|
226 \frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] |
|
227 Regular Expression\end{tabular}} |
|
228 |
|
229 \begin{textblock}{15}(1,4) |
|
230 \begin{tabular}{rcl} |
|
231 \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ |
|
232 \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
|
233 \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ |
|
234 \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ |
|
235 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\ |
|
236 \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star \quad\dn \bigcup_{0 \le n} L(r)^n$}\\ |
|
237 \end{tabular} |
|
238 \end{textblock} |
|
239 |
|
240 \begin{textblock}{6}(9,12)\small |
|
241 \bl{$L$} is a function from regular expressions to |
|
242 sets of strings\\ |
|
243 \bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
|
244 \end{textblock} |
|
245 |
|
246 \end{frame} |
|
247 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
248 |
|
249 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
250 \begin{frame}[c] |
|
251 \frametitle{\begin{tabular}{c}The Specification\\ of Matching\end{tabular}} |
|
252 |
|
253 \begin{bubble}[10cm] |
|
254 \large |
|
255 A regular expression \bl{$r$} matches a string~\bl{$s$} |
|
256 provided |
|
257 |
|
258 \begin{center} |
|
259 \bl{$s \in L(r)$}\\ |
|
260 \end{center} |
|
261 \end{bubble}\bigskip\bigskip |
|
262 |
|
263 \ldots and the point of the this lecture is |
|
264 to decide this problem as fast as possible |
|
265 (unlike Python, Ruby, Java etc) |
|
266 |
|
267 \end{frame} |
|
268 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
269 |
|
270 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
271 \begin{frame}[c] |
226 \frametitle{Semantic Derivative} |
272 \frametitle{Semantic Derivative} |
227 |
273 |
228 \begin{itemize} |
274 \begin{itemize} |
229 \item The \alert{\bf Semantic Derivative} of a |
275 \item The \alert{\bf Semantic Derivative} of a |
230 \underline{language}\\ wrt to a character \bl{$c$}: |
276 \underline{language}\\ wrt to a character \bl{$c$}: |
277 \begin{textblock}{9}(2,0.5) |
323 \begin{textblock}{9}(2,0.5) |
278 \begin{bubble}[9.8cm] |
324 \begin{bubble}[9.8cm] |
279 \lstinputlisting{../progs/app01.scala} |
325 \lstinputlisting{../progs/app01.scala} |
280 \end{bubble} |
326 \end{bubble} |
281 \end{textblock}} |
327 \end{textblock}} |
282 |
|
283 \end{frame} |
|
284 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
285 |
|
286 |
|
287 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
288 \begin{frame}[c] |
|
289 \frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}} |
|
290 |
|
291 \begin{textblock}{15}(1,4) |
|
292 \begin{tabular}{@ {}rcl} |
|
293 \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ |
|
294 \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
|
295 \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ |
|
296 \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ |
|
297 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ |
|
298 \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star$}\\ |
|
299 \end{tabular} |
|
300 \end{textblock} |
|
301 |
|
302 \begin{textblock}{6}(9,12)\small |
|
303 \bl{$L$} is a function from regular expressions to |
|
304 sets of strings\\ |
|
305 \bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
|
306 \end{textblock} |
|
307 |
|
308 \end{frame} |
|
309 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
310 |
|
311 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
312 \begin{frame}[c] |
|
313 |
|
314 \large |
|
315 \begin{center} |
|
316 What is \bl{$L(a^*)$}? |
|
317 \end{center} |
|
318 |
328 |
319 \end{frame} |
329 \end{frame} |
320 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
330 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
321 |
331 |
322 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
332 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |