123 \begin{tabular}{rcl} |
119 \begin{tabular}{rcl} |
124 \bl{$\textit{foo}\;@\;bar$} & \bl{$=$} & \bl{$\textit{foobar}$}\medskip\\ |
120 \bl{$\textit{foo}\;@\;bar$} & \bl{$=$} & \bl{$\textit{foobar}$}\medskip\\ |
125 \bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$} |
121 \bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$} |
126 \end{tabular} |
122 \end{tabular} |
127 \end{center} |
123 \end{center} |
128 |
124 \bigskip |
129 %\item The \alert{\bf meaning} of a regular expression is a set of |
125 |
130 % strings, or language. |
126 \small |
|
127 \item [] For example \bl{$A = \{foo, bar\}$}, \bl{$B = \{a, b\}$} |
|
128 |
|
129 \[ |
|
130 \bl{A \,@\, B = \{fooa, foob, bara, barb\}} |
|
131 \] |
|
132 |
131 \end{itemize} |
133 \end{itemize} |
132 |
134 |
133 \end{frame} |
135 \end{frame} |
134 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
136 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
135 |
137 |
136 |
138 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
137 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
139 \begin{frame}[c] |
138 \begin{frame}[t] |
140 \frametitle{The Power Operation} |
139 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
141 |
|
142 \begin{itemize} |
|
143 \item The \alert{\bf Power} of a language: |
|
144 |
|
145 \begin{center} |
|
146 \begin{tabular}{lcl} |
|
147 \bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
|
148 \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$} |
|
149 \end{tabular} |
|
150 \end{center}\bigskip |
|
151 |
|
152 \item[] For example |
|
153 |
|
154 \begin{center} |
|
155 \begin{tabular}{l} |
|
156 \bl{$A^4 = A \,@\, A \,@\, A \,@\, A$}\\ |
|
157 \bl{$A^0 \dn \{[]\}$}\\ |
|
158 \end{tabular} |
|
159 \end{center} |
|
160 |
|
161 \end{itemize} |
|
162 |
|
163 \end{frame} |
|
164 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
165 |
|
166 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
167 \begin{frame}[c] |
|
168 \frametitle{The Star Operation} |
|
169 |
|
170 \begin{itemize} |
|
171 \item The \alert{\bf Star} of a \underline{language}: |
|
172 \bigskip |
|
173 |
|
174 \begin{center} |
|
175 \begin{tabular}{c} |
|
176 \bl{$A^* \dn \bigcup_{0\le n} A^n$} |
|
177 \end{tabular} |
|
178 \end{center}\bigskip |
|
179 |
|
180 \item[] This expands to |
|
181 |
|
182 \[ |
|
183 \bl{A^0 \cup A^1 \cup A^2 \cup A^3 \cup A^4 \cup \ldots} |
|
184 \] |
|
185 |
|
186 \small |
|
187 \[ |
|
188 \bl{\{[]\} \;\cup\; A \;\cup\; A\,@\,A \;\cup\; |
|
189 A\,@\,A\,@\,A \;\cup\; A\,@\,A\,@\,A\,@\,A \cup \ldots} |
|
190 \] |
|
191 |
|
192 \end{itemize} |
|
193 |
|
194 \end{frame} |
|
195 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
196 |
|
197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
198 \begin{frame}[c] |
|
199 \frametitle{Semantic Derivative} |
|
200 |
|
201 \begin{itemize} |
|
202 \item The \alert{\bf Semantic Derivative} of a |
|
203 \underline{language}\\ wrt to a character \bl{$c$}: |
|
204 \bigskip |
|
205 |
|
206 \begin{center} |
|
207 \bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } |
|
208 \end{center}\bigskip\bigskip |
|
209 |
|
210 For \bl{$A = \{\textit{foo}, \textit{bar}, \textit{frak}\}$} then |
|
211 |
|
212 \begin{center} |
|
213 \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} |
|
214 $Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\ |
|
215 $Der\,b\,A$ & $=$ & $\{\textit{ar}\}$\\ |
|
216 $Der\,a\,A$ & $=$ & $\varnothing$\\ |
|
217 \end{tabular}} |
|
218 \end{center} |
|
219 |
|
220 \end{itemize} |
|
221 |
|
222 \end{frame} |
|
223 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
224 |
|
225 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
226 \begin{frame}[t] |
|
227 \frametitle{Regular Expressions} |
140 |
228 |
141 Their inductive definition: |
229 Their inductive definition: |
142 |
230 |
143 |
231 |
144 \begin{textblock}{6}(2,7.5) |
232 \begin{textblock}{6}(2,7.5) |
145 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
233 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
146 \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$} & null\\ |
234 \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$} & null\\ |
147 & \bl{$\mid$} & \bl{$\epsilon$} & empty string / \pcode{""} / $[]$\\ |
235 & \bl{$\mid$} & \bl{$\epsilon$} & empty string / \pcode{""} / $[]$\\ |
148 & \bl{$\mid$} & \bl{$c$} & character\\ |
236 & \bl{$\mid$} & \bl{$c$} & character\\ |
149 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\ |
237 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\ |
150 & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\ |
238 & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\ |
151 & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\ |
239 & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\ |
152 \end{tabular} |
240 \end{tabular} |
153 \end{textblock} |
241 \end{textblock} |
154 |
242 |
155 |
243 |
162 \frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}} |
250 \frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}} |
163 |
251 |
164 \begin{textblock}{15}(1,4) |
252 \begin{textblock}{15}(1,4) |
165 \begin{tabular}{@ {}rcl} |
253 \begin{tabular}{@ {}rcl} |
166 \bl{$L(\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$}\\ |
254 \bl{$L(\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$}\\ |
167 \bl{$L(\epsilon)$} & \bl{$\dn$} & \bl{$\{$[]$\}$}\\ |
255 \bl{$L(\epsilon)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
168 \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ |
256 \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ |
169 \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ |
257 \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ |
170 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ |
258 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ |
171 \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$\bigcup_{n \ge 0} L(r)^n$}\\ |
259 \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))^*$}\\ |
172 \end{tabular}\bigskip |
260 \end{tabular} |
173 |
|
174 \only<2->{ |
|
175 \hspace{5mm}\textcolor{blue}{$L(r)^0 \;\dn\; \{[]\}$}\\ |
|
176 \textcolor{blue}{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}} |
|
177 \end{textblock} |
261 \end{textblock} |
178 |
262 |
179 \only<1->{ |
|
180 \begin{textblock}{6}(9,12)\small |
263 \begin{textblock}{6}(9,12)\small |
181 \bl{$L$} is a function from regular expressions to sets of strings\\ |
264 \bl{$L$} is a function from regular expressions to sets of strings\\ |
182 \bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
265 \bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
183 \end{textblock}} |
266 \end{textblock} |
184 |
267 |
185 \end{frame} |
268 \end{frame} |
186 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
269 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
187 |
270 |
188 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
271 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
331 \item \bl{$(a + a \cdot a)^+$} |
412 \item \bl{$(a + a \cdot a)^+$} |
332 \item \bl{$(a + a?)^+$} |
413 \item \bl{$(a + a?)^+$} |
333 \end{itemize} |
414 \end{itemize} |
334 \end{itemize} |
415 \end{itemize} |
335 |
416 |
336 \end{frame}} |
417 \end{frame} |
337 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
418 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
338 |
419 |
339 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
420 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
340 \mode<presentation>{ |
421 \begin{frame}[t] |
341 \begin{frame}[t] |
422 \frametitle{A Matching Algorithm} |
342 \frametitle{\begin{tabular}{c}A Matching Algorithm\end{tabular}} |
|
343 |
423 |
344 |
424 |
345 \ldots{}whether a regular expression can match the empty string: |
425 \ldots{}whether a regular expression can match the empty string: |
346 \begin{center} |
426 \begin{center} |
347 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
427 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
348 \bl{$nullable(\varnothing)$} & \bl{$\dn$} & \bl{$f\!\/alse$}\\ |
428 \bl{$nullable(\varnothing)$} & \bl{$\dn$} & \bl{\textit{false}}\\ |
349 \bl{$nullable(\epsilon)$} & \bl{$\dn$} & \bl{$true$}\\ |
429 \bl{$nullable(\epsilon)$} & \bl{$\dn$} & \bl{\textit{true}}\\ |
350 \bl{$nullable (c)$} & \bl{$\dn$} & \bl{$f\!alse$}\\ |
430 \bl{$nullable (c)$} & \bl{$\dn$} & \bl{\textit{false}}\\ |
351 \bl{$nullable (r_1 + r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \vee nullable(r_2)$} \\ |
431 \bl{$nullable (r_1 + r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \vee nullable(r_2)$} \\ |
352 \bl{$nullable (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \wedge nullable(r_2)$} \\ |
432 \bl{$nullable (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \wedge nullable(r_2)$} \\ |
353 \bl{$nullable (r^*)$} & \bl{$\dn$} & \bl{$true$} \\ |
433 \bl{$nullable (r^*)$} & \bl{$\dn$} & \bl{\textit{true}}\\ |
354 \end{tabular} |
434 \end{tabular} |
355 \end{center} |
435 \end{center} |
356 |
436 |
357 \end{frame}} |
437 \end{frame} |
358 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
438 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
359 |
439 |
360 |
440 |
361 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
441 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
362 \mode<presentation>{ |
442 \begin{frame}[c] |
363 \begin{frame}[c] |
443 \frametitle{The Derivative of a Rexp} |
364 \frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}} |
|
365 |
444 |
366 \large |
445 \large |
367 If \bl{$r$} matches the string \bl{$c\!::\!s$}, what is a regular |
446 If \bl{$r$} matches the string \bl{$c\!::\!s$}, what is a regular |
368 expression that matches \bl{$s$}?\bigskip\bigskip\bigskip\bigskip |
447 expression that matches just \bl{$s$}?\bigskip\bigskip\bigskip\bigskip |
369 |
448 |
370 \small |
449 \small |
371 \bl{$der\,c\,r$} gives the answer, Brzozowski 1964 |
450 \bl{$der\,c\,r$} gives the answer, Brzozowski 1964 |
372 \end{frame}} |
451 \end{frame} |
373 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
452 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
374 |
453 |
375 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
454 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
376 \mode<presentation>{ |
455 \mode<presentation>{ |
377 \begin{frame}[c] |
456 \begin{frame}[c] |
378 \frametitle{\begin{tabular}{c}The Derivative of a Rexp (2)\end{tabular}} |
457 \frametitle{The Derivative of a Rexp} |
379 |
458 |
380 \begin{center} |
459 \begin{center} |
381 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
460 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
382 \bl{$der\, c\, (\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
461 \bl{$der\, c\, (\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
383 \bl{$der\, c\, (\epsilon)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
462 \bl{$der\, c\, (\epsilon)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
384 \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\ |
463 \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\ |
385 \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\ |
464 \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\ |
386 \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ |
465 \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ |
387 & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ |
466 & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ |
388 & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\ |
467 & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\ |
389 \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\\pause |
468 \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\bigskip\\\pause |
390 |
469 |
391 \bl{$\textit{ders}\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ |
470 \bl{$\textit{ders}\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ |
392 \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\ |
471 \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\ |
393 \end{tabular} |
472 \end{tabular} |
394 \end{center} |
473 \end{center} |
395 |
474 |
396 \end{frame}} |
475 \end{frame}} |
397 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
476 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
398 |
477 |
399 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
478 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
400 \mode<presentation>{ |
479 \begin{frame}[c] |
401 \begin{frame}[c] |
480 \frametitle{Examples} |
402 \frametitle{\begin{tabular}{c}Examples\end{tabular}} |
|
403 |
481 |
404 Given \bl{$r \dn ((a \cdot b) + b)^*$} what is |
482 Given \bl{$r \dn ((a \cdot b) + b)^*$} what is |
405 |
483 |
406 \begin{center} |
484 \begin{center} |
407 \begin{tabular}{l} |
485 \begin{tabular}{l} |
408 \bl{$der\,a\,r =?$}\\ |
486 \bl{$der\,a\,r =\;?$}\\ |
409 \bl{$der\,b\,r =?$}\\ |
487 \bl{$der\,b\,r =\;?$}\\ |
410 \bl{$der\,c\,r =?$} |
488 \bl{$der\,c\,r =\;?$} |
411 \end{tabular} |
489 \end{tabular} |
412 \end{center} |
490 \end{center} |
413 |
491 |
414 |
492 \end{frame} |
415 \end{frame}} |
|
416 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
493 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
417 |
494 |
418 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
495 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
419 \mode<presentation>{ |
496 \mode<presentation>{ |
420 \begin{frame}[t] |
497 \begin{frame}[t] |
428 Step 3: & build derivative of \bl{$c$} and \bl{$r_3$} & \bl{$(r_4 = der\,b\,r_3)$}\smallskip\\ |
505 Step 3: & build derivative of \bl{$c$} and \bl{$r_3$} & \bl{$(r_4 = der\,b\,r_3)$}\smallskip\\ |
429 Step 4: & the string is exhausted; test & (\bl{$nullable(r_4)$})\\ |
506 Step 4: & the string is exhausted; test & (\bl{$nullable(r_4)$})\\ |
430 & whether \bl{$r_4$} can recognise\\ |
507 & whether \bl{$r_4$} can recognise\\ |
431 & the empty string\smallskip\\ |
508 & the empty string\smallskip\\ |
432 Output: & result of the test\\ |
509 Output: & result of the test\\ |
433 & $\Rightarrow true \,\text{or}\, \textit{false}$\\ |
510 & $\Rightarrow \bl{\textit{true}} \,\text{or}\, |
|
511 \bl{\textit{false}}$\\ |
434 \end{tabular} |
512 \end{tabular} |
435 \end{center} |
513 \end{center} |
436 |
514 |
437 |
515 |
438 \end{frame}} |
516 \end{frame}} |
439 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
517 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
440 |
518 |
441 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
519 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
442 \mode<presentation>{ |
520 \begin{frame}[c] |
|
521 \frametitle{The Idea of the Algorithm} |
|
522 |
|
523 If we want to recognise the string \bl{$abc$} with regular |
|
524 expression \bl{$r_1$} then\medskip |
|
525 |
|
526 \begin{enumerate} |
|
527 \item \bl{$Der\,a\,(L(r_1))$}\pause |
|
528 \item \bl{$Der\,b\,(Der\,a\,(L(r_1)))$}\pause |
|
529 \item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r_1))))$}\bigskip |
|
530 \item finally we test whether the empty string is in this set\medskip |
|
531 \end{enumerate} |
|
532 |
|
533 The matching algorithm works similarly, just over regular expressions instead of sets. |
|
534 \end{frame} |
|
535 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
536 |
|
537 |
|
538 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
443 \begin{frame}[c] |
539 \begin{frame}[c] |
444 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
540 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
445 |
541 |
446 \begin{center} |
542 \begin{center} |
447 \begin{tikzpicture} |
543 \begin{tikzpicture} |