1 \documentclass[dvipsnames,14pt,t]{beamer} |
|
2 \usepackage{beamerthemeplainculight} |
|
3 \usepackage[T1]{fontenc} |
|
4 \usepackage[latin1]{inputenc} |
|
5 \usepackage{mathpartir} |
|
6 \usepackage[absolute,overlay]{textpos} |
|
7 \usepackage{ifthen} |
|
8 \usepackage{tikz} |
|
9 \usepackage{pgf} |
|
10 \usepackage{calc} |
|
11 \usepackage{ulem} |
|
12 \usepackage{courier} |
|
13 \usepackage{listings} |
|
14 \renewcommand{\uline}[1]{#1} |
|
15 \usetikzlibrary{arrows} |
|
16 \usetikzlibrary{automata} |
|
17 \usetikzlibrary{shapes} |
|
18 \usetikzlibrary{shadows} |
|
19 \usetikzlibrary{positioning} |
|
20 \usetikzlibrary{calc} |
|
21 \usepackage{graphicx} |
|
22 |
|
23 \definecolor{javared}{rgb}{0.6,0,0} % for strings |
|
24 \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments |
|
25 \definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords |
|
26 \definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc |
|
27 |
|
28 \lstset{language=Java, |
|
29 basicstyle=\ttfamily, |
|
30 keywordstyle=\color{javapurple}\bfseries, |
|
31 stringstyle=\color{javagreen}, |
|
32 commentstyle=\color{javagreen}, |
|
33 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
|
34 numbers=left, |
|
35 numberstyle=\tiny\color{black}, |
|
36 stepnumber=1, |
|
37 numbersep=10pt, |
|
38 tabsize=2, |
|
39 showspaces=false, |
|
40 showstringspaces=false} |
|
41 |
|
42 \lstdefinelanguage{scala}{ |
|
43 morekeywords={abstract,case,catch,class,def,% |
|
44 do,else,extends,false,final,finally,% |
|
45 for,if,implicit,import,match,mixin,% |
|
46 new,null,object,override,package,% |
|
47 private,protected,requires,return,sealed,% |
|
48 super,this,throw,trait,true,try,% |
|
49 type,val,var,while,with,yield}, |
|
50 otherkeywords={=>,<-,<\%,<:,>:,\#,@}, |
|
51 sensitive=true, |
|
52 morecomment=[l]{//}, |
|
53 morecomment=[n]{/*}{*/}, |
|
54 morestring=[b]", |
|
55 morestring=[b]', |
|
56 morestring=[b]""" |
|
57 } |
|
58 |
|
59 \lstset{language=Scala, |
|
60 basicstyle=\ttfamily, |
|
61 keywordstyle=\color{javapurple}\bfseries, |
|
62 stringstyle=\color{javagreen}, |
|
63 commentstyle=\color{javagreen}, |
|
64 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
|
65 numbers=left, |
|
66 numberstyle=\tiny\color{black}, |
|
67 stepnumber=1, |
|
68 numbersep=10pt, |
|
69 tabsize=2, |
|
70 showspaces=false, |
|
71 showstringspaces=false} |
|
72 |
|
73 % beamer stuff |
|
74 \renewcommand{\slidecaption}{AFL 04, King's College London, 17.~October 2012} |
|
75 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
|
76 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions |
|
77 |
|
78 \begin{document} |
|
79 |
|
80 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
81 \mode<presentation>{ |
|
82 \begin{frame}<1>[t] |
|
83 \frametitle{% |
|
84 \begin{tabular}{@ {}c@ {}} |
|
85 \\[-3mm] |
|
86 \LARGE Automata and \\[-2mm] |
|
87 \LARGE Formal Languages (4)\\[3mm] |
|
88 \end{tabular}} |
|
89 |
|
90 \normalsize |
|
91 \begin{center} |
|
92 \begin{tabular}{ll} |
|
93 Email: & christian.urban at kcl.ac.uk\\ |
|
94 Of$\!$fice: & S1.27 (1st floor Strand Building)\\ |
|
95 Slides: & KEATS (also home work is there)\\ |
|
96 \end{tabular} |
|
97 \end{center} |
|
98 |
|
99 |
|
100 \end{frame}} |
|
101 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
102 |
|
103 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
104 \mode<presentation>{ |
|
105 \begin{frame}[c] |
|
106 \frametitle{\begin{tabular}{c}Last Week\end{tabular}} |
|
107 |
|
108 Last week I showed you\bigskip |
|
109 |
|
110 \begin{itemize} |
|
111 \item a tokenizer taking a list of regular expressions\bigskip |
|
112 |
|
113 \item tokenization identifies lexeme in an input stream of characters (or string) |
|
114 and cathegorizes them into tokens |
|
115 |
|
116 \end{itemize} |
|
117 |
|
118 \end{frame}} |
|
119 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
120 |
|
121 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
122 \mode<presentation>{ |
|
123 \begin{frame}[c] |
|
124 \frametitle{\begin{tabular}{c}Two Rules\end{tabular}} |
|
125 |
|
126 \begin{itemize} |
|
127 \item Longest match rule (maximal munch rule): The |
|
128 longest initial substring matched by any regular expression is taken |
|
129 as next token.\bigskip |
|
130 |
|
131 \item Rule priority: |
|
132 For a particular longest initial substring, the first regular |
|
133 expression that can match determines the token. |
|
134 |
|
135 \end{itemize} |
|
136 |
|
137 %\url{http://www.technologyreview.com/tr10/?year=2011} |
|
138 |
|
139 %finite deterministic automata/ nondeterministic automaton |
|
140 |
|
141 %\item problem with infix operations, for example i-12 |
|
142 |
|
143 |
|
144 \end{frame}} |
|
145 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
146 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
147 |
|
148 \mode<presentation>{ |
|
149 \begin{frame}[t] |
|
150 |
|
151 \begin{center} |
|
152 \texttt{"if true then then 42 else +"} |
|
153 \end{center} |
|
154 |
|
155 |
|
156 \begin{tabular}{@{}l} |
|
157 KEYWORD: \\ |
|
158 \hspace{5mm}\texttt{"if"}, \texttt{"then"}, \texttt{"else"},\\ |
|
159 WHITESPACE:\\ |
|
160 \hspace{5mm}\texttt{" "}, \texttt{"$\backslash$n"},\\ |
|
161 IDENT:\\ |
|
162 \hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + \texttt{"\_"})$^*$\\ |
|
163 NUM:\\ |
|
164 \hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + \texttt{"0"}\\ |
|
165 OP:\\ |
|
166 \hspace{5mm}\texttt{"+"}\\ |
|
167 COMMENT:\\ |
|
168 \hspace{5mm}\texttt{"$\slash$*"} $\cdot$ (ALL$^*$ $\cdot$ \texttt{"*$\slash$"} $\cdot$ ALL$^*$) $\cdot$ \texttt{"*$\slash$"} |
|
169 \end{tabular} |
|
170 |
|
171 \end{frame}} |
|
172 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
173 |
|
174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
175 \mode<presentation>{ |
|
176 \begin{frame}[t] |
|
177 |
|
178 \begin{center} |
|
179 \texttt{"if true then then 42 else +"} |
|
180 \end{center} |
|
181 |
|
182 \only<1>{ |
|
183 \small\begin{tabular}{l} |
|
184 KEYWORD(if),\\ |
|
185 WHITESPACE,\\ |
|
186 IDENT(true),\\ |
|
187 WHITESPACE,\\ |
|
188 KEYWORD(then),\\ |
|
189 WHITESPACE,\\ |
|
190 KEYWORD(then),\\ |
|
191 WHITESPACE,\\ |
|
192 NUM(42),\\ |
|
193 WHITESPACE,\\ |
|
194 KEYWORD(else),\\ |
|
195 WHITESPACE,\\ |
|
196 OP(+) |
|
197 \end{tabular}} |
|
198 |
|
199 \only<2>{ |
|
200 \small\begin{tabular}{l} |
|
201 KEYWORD(if),\\ |
|
202 IDENT(true),\\ |
|
203 KEYWORD(then),\\ |
|
204 KEYWORD(then),\\ |
|
205 NUM(42),\\ |
|
206 KEYWORD(else),\\ |
|
207 OP(+) |
|
208 \end{tabular}} |
|
209 |
|
210 \end{frame}} |
|
211 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
212 |
|
213 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
214 \mode<presentation>{ |
|
215 \begin{frame}[c] |
|
216 |
|
217 |
|
218 There is one small problem with the tokenizer. How should we |
|
219 tokenize: |
|
220 |
|
221 \begin{center} |
|
222 \texttt{"x - 3"} |
|
223 \end{center} |
|
224 |
|
225 \begin{tabular}{@{}l} |
|
226 OP:\\ |
|
227 \hspace{5mm}\texttt{"+"}, \texttt{"-"}\\ |
|
228 NUM:\\ |
|
229 \hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + \texttt{"0"}\\ |
|
230 NUMBER:\\ |
|
231 \hspace{5mm}NUM + (\texttt{"-"} $\cdot$ NUM)\\ |
|
232 \end{tabular} |
|
233 |
|
234 |
|
235 \end{frame}} |
|
236 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
237 |
|
238 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
239 \mode<presentation>{ |
|
240 \begin{frame}[c] |
|
241 \frametitle{\begin{tabular}{c}Negation\end{tabular}} |
|
242 |
|
243 Assume you have an alphabet consisting of the letters \bl{a}, \bl{b} and \bl{c} only. |
|
244 Find a regular expression that matches all strings \emph{except} \bl{ab}, \bl{ac} and \bl{cba}. |
|
245 |
|
246 \end{frame}} |
|
247 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
248 |
|
249 |
|
250 |
|
251 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
252 \mode<presentation>{ |
|
253 \begin{frame}[c] |
|
254 \frametitle{\begin{tabular}{c}Deterministic Finite Automata\end{tabular}} |
|
255 |
|
256 A deterministic finite automaton consists of: |
|
257 |
|
258 \begin{itemize} |
|
259 \item a finite set of states |
|
260 \item one of these states is the start state |
|
261 \item some states are accepting states, and |
|
262 \item there is transition function\medskip |
|
263 |
|
264 \small |
|
265 which takes a state and a character as arguments and produces a new state\smallskip\\ |
|
266 this function might not always be defined everywhere |
|
267 \end{itemize} |
|
268 |
|
269 \begin{center} |
|
270 \bl{$A(Q, q_0, F, \delta)$} |
|
271 \end{center} |
|
272 \end{frame}} |
|
273 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
274 |
|
275 |
|
276 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
277 \mode<presentation>{ |
|
278 \begin{frame}[c] |
|
279 |
|
280 \begin{center} |
|
281 \includegraphics[scale=0.7]{pics/ch3.jpg} |
|
282 \end{center}\pause |
|
283 |
|
284 \begin{itemize} |
|
285 \item start can be an accepting state |
|
286 \item it is possible that there is no accepting state |
|
287 \item all states might be accepting (but does not necessarily mean all strings are accepted) |
|
288 \end{itemize} |
|
289 |
|
290 \end{frame}} |
|
291 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
292 |
|
293 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
294 \mode<presentation>{ |
|
295 \begin{frame}[c] |
|
296 |
|
297 \begin{center} |
|
298 \includegraphics[scale=0.7]{pics/ch3.jpg} |
|
299 \end{center} |
|
300 |
|
301 for this automaton \bl{$\delta$} is the function\\ |
|
302 |
|
303 \begin{center} |
|
304 \begin{tabular}{lll} |
|
305 \bl{(q$_0$, a) $\rightarrow$ q$_1$} & \bl{(q$_1$, a) $\rightarrow$ q$_4$} & \bl{(q$_4$, a) $\rightarrow$ q$_4$}\\ |
|
306 \bl{(q$_0$, b) $\rightarrow$ q$_2$} & \bl{(q$_1$, b) $\rightarrow$ q$_2$} & \bl{(q$_4$, b) $\rightarrow$ q$_4$}\\ |
|
307 \end{tabular}\ldots |
|
308 \end{center} |
|
309 |
|
310 \end{frame}} |
|
311 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
312 |
|
313 |
|
314 |
|
315 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
316 \mode<presentation>{ |
|
317 \begin{frame}[t] |
|
318 \frametitle{\begin{tabular}{c}Accepting a String\end{tabular}} |
|
319 |
|
320 Given |
|
321 |
|
322 \begin{center} |
|
323 \bl{$A(Q, q_0, F, \delta)$} |
|
324 \end{center} |
|
325 |
|
326 you can define |
|
327 |
|
328 \begin{center} |
|
329 \begin{tabular}{l} |
|
330 \bl{$\hat{\delta}(q, \texttt{""}) = q$}\\ |
|
331 \bl{$\hat{\delta}(q, c::s) = \hat{\delta}(\delta(q, c), s)$}\\ |
|
332 \end{tabular} |
|
333 \end{center}\pause |
|
334 |
|
335 Whether a string \bl{$s$} is accepted by \bl{$A$}? |
|
336 |
|
337 \begin{center} |
|
338 \hspace{5mm}\bl{$\hat{\delta}(q_0, s) \in F$} |
|
339 \end{center} |
|
340 \end{frame}} |
|
341 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
342 |
|
343 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
344 \mode<presentation>{ |
|
345 \begin{frame}[c] |
|
346 \frametitle{\begin{tabular}{c}Non-Deterministic\\[-1mm] Finite Automata\end{tabular}} |
|
347 |
|
348 A non-deterministic finite automaton consists again of: |
|
349 |
|
350 \begin{itemize} |
|
351 \item a finite set of states |
|
352 \item one of these states is the start state |
|
353 \item some states are accepting states, and |
|
354 \item there is transition \alert{relation}\medskip |
|
355 \end{itemize} |
|
356 |
|
357 |
|
358 \begin{center} |
|
359 \begin{tabular}{c} |
|
360 \bl{(q$_1$, a) $\rightarrow$ q$_2$}\\ |
|
361 \bl{(q$_1$, a) $\rightarrow$ q$_3$}\\ |
|
362 \end{tabular} |
|
363 \hspace{10mm} |
|
364 \begin{tabular}{c} |
|
365 \bl{(q$_1$, $\epsilon$) $\rightarrow$ q$_2$}\\ |
|
366 \end{tabular} |
|
367 \end{center} |
|
368 |
|
369 \end{frame}} |
|
370 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
371 |
|
372 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
373 \mode<presentation>{ |
|
374 \begin{frame}[c] |
|
375 |
|
376 \begin{center} |
|
377 \includegraphics[scale=0.7]{pics/ch5.jpg} |
|
378 \end{center} |
|
379 |
|
380 |
|
381 \end{frame}} |
|
382 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
383 |
|
384 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
385 \mode<presentation>{ |
|
386 \begin{frame}[c] |
|
387 |
|
388 \begin{center} |
|
389 \begin{tabular}[b]{ll} |
|
390 \bl{$\varnothing$} & \includegraphics[scale=0.7]{pics/NULL.jpg}\\\\ |
|
391 \bl{$\epsilon$} & \includegraphics[scale=0.7]{pics/epsilon.jpg}\\\\ |
|
392 \bl{c} & \includegraphics[scale=0.7]{pics/char.jpg}\\ |
|
393 \end{tabular} |
|
394 \end{center} |
|
395 |
|
396 \end{frame}} |
|
397 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
398 |
|
399 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
400 \mode<presentation>{ |
|
401 \begin{frame}[c] |
|
402 |
|
403 \begin{center} |
|
404 \begin{tabular}[t]{ll} |
|
405 \bl{r$_1$ $\cdot$ r$_2$} & \includegraphics[scale=0.6]{pics/seq.jpg}\\\\ |
|
406 \end{tabular} |
|
407 \end{center} |
|
408 |
|
409 \end{frame}} |
|
410 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
411 |
|
412 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
413 \mode<presentation>{ |
|
414 \begin{frame}[c] |
|
415 |
|
416 \begin{center} |
|
417 \begin{tabular}[t]{ll} |
|
418 \bl{r$_1$ + r$_2$} & \includegraphics[scale=0.7]{pics/alt.jpg}\\\\ |
|
419 \end{tabular} |
|
420 \end{center} |
|
421 |
|
422 \end{frame}} |
|
423 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
424 |
|
425 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
426 \mode<presentation>{ |
|
427 \begin{frame}[c] |
|
428 |
|
429 \begin{center} |
|
430 \begin{tabular}[b]{ll} |
|
431 \bl{r$^*$} & \includegraphics[scale=0.7]{pics/star.jpg}\\ |
|
432 \end{tabular} |
|
433 \end{center}\pause\bigskip |
|
434 |
|
435 Why can't we just have an epsilon transition from the accepting states to the starting state? |
|
436 |
|
437 \end{frame}} |
|
438 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
439 |
|
440 |
|
441 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
442 \mode<presentation>{ |
|
443 \begin{frame}[c] |
|
444 \frametitle{\begin{tabular}{c}Subset Construction\end{tabular}} |
|
445 |
|
446 |
|
447 \begin{textblock}{5}(1,2.5) |
|
448 \includegraphics[scale=0.5]{pics/ch5.jpg} |
|
449 \end{textblock} |
|
450 |
|
451 \begin{textblock}{11}(6.5,4.5) |
|
452 \begin{tabular}{r|cl} |
|
453 & a & b\\ |
|
454 \hline |
|
455 $\varnothing$ \onslide<2>{\textcolor{white}{*}} & $\varnothing$ & $\varnothing$\\ |
|
456 $\{0\}$ \onslide<2>{\textcolor{white}{*}} & $\{0,1,2\}$ & $\{2\}$\\ |
|
457 $\{1\}$ \onslide<2>{\textcolor{white}{*}} &$\{1\}$ & $\varnothing$\\ |
|
458 $\{2\}$ \onslide<2>{*} & $\varnothing$ &$\{2\}$\\ |
|
459 $\{0,1\}$ \onslide<2>{\textcolor{white}{*}} &$\{0,1,2\}$ &$\{2\}$\\ |
|
460 $\{0,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\ |
|
461 $\{1,2\}$ \onslide<2>{*}& $\{1\}$ & $\{2\}$\\ |
|
462 \onslide<2>{s:} $\{0,1,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\ |
|
463 \end{tabular} |
|
464 \end{textblock} |
|
465 |
|
466 |
|
467 \end{frame}} |
|
468 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
469 |
|
470 |
|
471 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
472 \mode<presentation>{ |
|
473 \begin{frame}[c] |
|
474 \frametitle{\begin{tabular}{c}Regular Languages\end{tabular}} |
|
475 |
|
476 A language is \alert{regular} iff there exists |
|
477 a regular expression that recognises all its strings.\bigskip\medskip |
|
478 |
|
479 or equivalently\bigskip\medskip |
|
480 |
|
481 A language is \alert{regular} iff there exists |
|
482 a deterministic finite automaton that recognises all its strings.\bigskip\pause |
|
483 |
|
484 Why is every finite set of strings a regular language? |
|
485 \end{frame}} |
|
486 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
487 |
|
488 |
|
489 |
|
490 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
491 \mode<presentation>{ |
|
492 \begin{frame}[c] |
|
493 |
|
494 \begin{center} |
|
495 \includegraphics[scale=0.5]{pics/ch3.jpg} |
|
496 \end{center} |
|
497 |
|
498 \begin{center} |
|
499 \includegraphics[scale=0.5]{pics/ch4.jpg}\\ |
|
500 minimal automaton |
|
501 \end{center} |
|
502 |
|
503 \end{frame}} |
|
504 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
505 |
|
506 |
|
507 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
508 \mode<presentation>{ |
|
509 \begin{frame}[c] |
|
510 |
|
511 \begin{enumerate} |
|
512 \item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p} |
|
513 \item Mark all pairs that accepting and non-accepting states |
|
514 \item For all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether |
|
515 \begin{center} |
|
516 \bl{($\delta$(q,c), $\delta$(p,c))} |
|
517 \end{center} |
|
518 are marked. If yes, then also mark \bl{(q, p)} |
|
519 \item Repeat last step until no chance. |
|
520 \item All unmarked pairs can be merged. |
|
521 \end{enumerate} |
|
522 |
|
523 \end{frame}} |
|
524 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
525 |
|
526 |
|
527 |
|
528 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
529 \mode<presentation>{ |
|
530 \begin{frame}[c] |
|
531 |
|
532 Given the function |
|
533 |
|
534 \begin{center} |
|
535 \bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l} |
|
536 $rev(\varnothing)$ & $\dn$ & $\varnothing$\\ |
|
537 $rev(\epsilon)$ & $\dn$ & $\epsilon$\\ |
|
538 $rev(c)$ & $\dn$ & $c$\\ |
|
539 $rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ |
|
540 $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ |
|
541 $rev(r^*)$ & $\dn$ & $rev(r)^*$\\ |
|
542 \end{tabular}} |
|
543 \end{center} |
|
544 |
|
545 |
|
546 and the set |
|
547 |
|
548 \begin{center} |
|
549 \bl{$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$} |
|
550 \end{center} |
|
551 |
|
552 prove whether |
|
553 |
|
554 \begin{center} |
|
555 \bl{$L(rev(r)) = Rev (L(r))$} |
|
556 \end{center} |
|
557 |
|
558 \end{frame}} |
|
559 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
560 |
|
561 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
562 \mode<presentation>{ |
|
563 \begin{frame}[c] |
|
564 |
|
565 \begin{itemize} |
|
566 \item The star-case in our proof about the matcher needs the following lemma |
|
567 \begin{center} |
|
568 \bl{Der\,c\,A$^*$ $=$ (Der c A)\,@\, A$^*$} |
|
569 \end{center} |
|
570 \end{itemize}\bigskip\bigskip |
|
571 |
|
572 \begin{itemize} |
|
573 \item If \bl{\texttt{""} $\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B $\cup$ (Der\,c\,B)}\medskip |
|
574 \item If \bl{\texttt{""} $\not\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B} |
|
575 |
|
576 \end{itemize} |
|
577 |
|
578 \end{frame}} |
|
579 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
580 |
|
581 |
|
582 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
583 \mode<presentation>{ |
|
584 \begin{frame}[c] |
|
585 |
|
586 \begin{itemize} |
|
587 \item Assuming you have the alphabet \bl{\{a, b, c\}}\bigskip |
|
588 \item Give a regular expression that can recognise all strings that have at least one \bl{b}. |
|
589 \end{itemize} |
|
590 |
|
591 \end{frame}} |
|
592 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
593 |
|
594 |
|
595 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
596 \mode<presentation>{ |
|
597 \begin{frame}[c] |
|
598 |
|
599 ``I hate coding. I do not want to look at code.'' |
|
600 |
|
601 \end{frame}} |
|
602 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
603 |
|
604 |
|
605 |
|
606 \end{document} |
|
607 |
|
608 %%% Local Variables: |
|
609 %%% mode: latex |
|
610 %%% TeX-master: t |
|
611 %%% End: |
|
612 |
|