25 \begin{frame}[t] |
25 \begin{frame}[t] |
26 \frametitle{% |
26 \frametitle{% |
27 \begin{tabular}{@ {}c@ {}} |
27 \begin{tabular}{@ {}c@ {}} |
28 \\[-3mm] |
28 \\[-3mm] |
29 \LARGE Compilers and \\[-2mm] |
29 \LARGE Compilers and \\[-2mm] |
30 \LARGE Formal Languages (4)\\[3mm] |
30 \LARGE Formal Languages\\[3mm] |
31 \end{tabular}} |
31 \end{tabular}} |
32 |
32 |
33 \normalsize |
33 \normalsize |
34 \begin{center} |
34 \begin{center} |
35 \begin{tabular}{ll} |
35 \begin{tabular}{ll} |
36 Email: & christian.urban at kcl.ac.uk\\ |
36 Email: & christian.urban at kcl.ac.uk\\ |
37 Office Hours: & Thursdays 12 -- 14\\ |
37 %Office Hours: & Thursdays 12 -- 14\\ |
38 Location: & N7.07 (North Wing, Bush House)\\ |
38 %Location: & N7.07 (North Wing, Bush House)\\ |
39 Slides \& Progs: & KEATS (also homework is there)\\ |
39 Slides \& Progs: & KEATS (also homework is there)\\ |
40 \end{tabular} |
40 \end{tabular} |
41 \end{center} |
41 \end{center} |
42 |
42 |
43 \end{frame} |
43 |
44 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
44 \begin{center} |
45 |
45 \begin{tikzpicture} |
46 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
46 \node[drop shadow,fill=white,inner sep=0pt] |
47 \begin{frame}[c] |
47 {\footnotesize\rowcolors{1}{capri!10}{white} |
48 |
48 \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline |
49 \begin{center} |
49 1 Introduction, Languages & 6 While-Language \\ |
50 \begin{tikzpicture}[scale=2,>=stealth',very thick, |
50 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\ |
51 every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] |
51 3 Automata, Regular Languages & 8 Compiling Functional Languages \\ |
52 \only<-7>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};} |
52 \cellcolor{blue!50} |
53 \only<8->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};} |
53 4 Lexing, Tokenising & 9 Optimisations \\ |
54 \only<-7>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};} |
54 5 Grammars, Parsing & 10 LLVM \\ \hline |
55 \only<8->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};} |
55 \end{tabular}% |
56 \node[state] (q2) at ( 2,1) {$\mbox{Q}_2$}; |
56 }; |
57 \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) |
57 \end{tikzpicture} |
58 (q1) edge[bend left] node[above] {\alert{$b$}} (q0) |
58 \end{center} |
59 (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) |
59 \end{frame} |
60 (q1) edge node[above] {\alert{$a$}} (q2) |
60 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
61 (q2) edge [loop right] node {\alert{$a$}} () |
|
62 (q0) edge [loop below] node {\alert{$b$}} () |
|
63 ; |
|
64 \end{tikzpicture} |
|
65 \end{center}\bigskip |
|
66 |
|
67 \begin{center} |
|
68 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
|
69 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b + \mbox{Q}_2\,b$}\\ |
|
70 \bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\ |
|
71 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\ |
|
72 \end{tabular} |
|
73 \end{center} |
|
74 |
|
75 |
|
76 Arden's Lemma: |
|
77 \begin{center} |
|
78 If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} |
|
79 \end{center} |
|
80 |
|
81 \only<2-6>{\small |
|
82 \begin{textblock}{6}(1,0.8) |
|
83 \begin{bubble}[6.7cm] |
|
84 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
85 \multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} \& \bl{$\mbox{Q}_2$}:}\\ |
|
86 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b + \mbox{Q}_2\,b$}\\ |
|
87 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} |
|
88 \end{tabular} |
|
89 \end{bubble} |
|
90 \end{textblock}} |
|
91 |
|
92 \only<3-6>{\small |
|
93 \begin{textblock}{6}(2,4.15) |
|
94 \begin{bubble}[6.7cm] |
|
95 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
96 \multicolumn{3}{@{}l}{simplifying \bl{$\mbox{Q}_0$}:}\\ |
|
97 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\ |
|
98 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} |
|
99 \end{tabular} |
|
100 \end{bubble} |
|
101 \end{textblock}} |
|
102 |
|
103 \only<4-6>{\small |
|
104 \begin{textblock}{6}(3,7.55) |
|
105 \begin{bubble}[6.7cm] |
|
106 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
107 \multicolumn{3}{@{}l}{Arden for \bl{$\mbox{Q}_2$}:}\\ |
|
108 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\ |
|
109 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$} |
|
110 \end{tabular} |
|
111 \end{bubble} |
|
112 \end{textblock}} |
|
113 |
|
114 \only<5-6>{\small |
|
115 \begin{textblock}{6}(4,10.9) |
|
116 \begin{bubble}[7.5cm] |
|
117 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
118 \multicolumn{3}{@{}l}{Substitute \bl{$\mbox{Q}_2$} and simplify:}\\ |
|
119 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b)$}\\ |
|
120 \end{tabular} |
|
121 \end{bubble} |
|
122 \end{textblock}} |
|
123 |
|
124 \only<6>{\small |
|
125 \begin{textblock}{6}(5,13.4) |
|
126 \begin{bubble}[7.5cm] |
|
127 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
128 \multicolumn{3}{@{}l}{Arden again for \bl{$\mbox{Q}_0$}:}\\ |
|
129 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\ |
|
130 \end{tabular} |
|
131 \end{bubble} |
|
132 \end{textblock}} |
|
133 |
|
134 |
|
135 \only<7->{\small |
|
136 \begin{textblock}{6}(6,11.5) |
|
137 \begin{bubble}[6.7cm] |
|
138 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
139 \multicolumn{3}{@{}l}{Finally:}\\ |
|
140 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\ |
|
141 \bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a$}\\ |
|
142 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a^*)$}\\ |
|
143 \end{tabular} |
|
144 \end{bubble} |
|
145 \end{textblock}} |
|
146 |
|
147 \end{frame} |
|
148 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
149 |
61 |
150 |
62 |
151 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
63 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
152 \begin{frame}[c] |
64 \begin{frame}[c] |
153 \frametitle{Coursework} |
65 \frametitle{Coursework} |
190 \quad\bl{\texttt{CFUN((c: Char) => true)}}\\ |
102 \quad\bl{\texttt{CFUN((c: Char) => true)}}\\ |
191 \end{tabular} |
103 \end{tabular} |
192 \end{center} |
104 \end{center} |
193 \end{frame} |
105 \end{frame} |
194 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
106 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
195 |
107 |
196 |
|
197 |
|
198 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
199 \begin{frame}[c] |
|
200 \frametitle{Regexps and Automata} |
|
201 |
|
202 \begin{center} |
|
203 \begin{tikzpicture} |
|
204 \node (rexp) {\bl{\bf Regexps}}; |
|
205 \node (nfa) [right=of rexp] {\bl{\bf NFAs}}; |
|
206 \node (dfa) [right=of nfa] {\bl{\bf DFAs}}; |
|
207 \node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}}; |
|
208 \path[->,red, line width=2mm] (rexp) edge node [above=4mm, black] |
|
209 {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa); |
|
210 \path[->,red, line width=2mm] (nfa) edge node [above=4mm, black] |
|
211 {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa); |
|
212 \path[->, red, line width=2mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa); |
|
213 %%\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp); |
|
214 \path[->, red, line width=2mm] (dfa) edge [bend left=45] node [below, black] {\begin{tabular}{l}Brzozowski's\\ method\end{tabular}} (rexp); |
|
215 |
|
216 \end{tikzpicture}\\ |
|
217 \end{center} |
|
218 |
|
219 \end{frame} |
|
220 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
221 |
|
222 |
|
223 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
224 \begin{frame}[t] |
|
225 \frametitle{\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}} |
|
226 |
|
227 \begin{tikzpicture} |
|
228 \begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs}, |
|
229 enlargelimits=false, |
|
230 xtick={0,5,...,30}, |
|
231 xmax=30, |
|
232 ymax=35, |
|
233 ytick={0,5,...,30}, |
|
234 scaled ticks=false, |
|
235 axis lines=left, |
|
236 width=10cm, |
|
237 height=7cm, |
|
238 legend entries={Python,Ruby,my NFA}, |
|
239 legend pos=north west, |
|
240 legend cell align=left] |
|
241 \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; |
|
242 \addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; |
|
243 \addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data}; |
|
244 \end{axis} |
|
245 \end{tikzpicture} |
|
246 |
|
247 The punchline is that many existing libraries do depth-first search |
|
248 in NFAs (backtracking). |
|
249 |
|
250 \end{frame} |
|
251 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
252 |
|
253 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
254 % \begin{frame}[c] |
|
255 % \frametitle{DFA to Rexp} |
|
256 |
|
257 % \begin{center} |
|
258 % \begin{tikzpicture}[scale=2,>=stealth',very thick, |
|
259 % every state/.style={minimum size=0pt, |
|
260 % draw=blue!50,very thick,fill=blue!20},] |
|
261 % \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
|
262 % \node[state] (q1) at ( 1,1) {$q_1$}; |
|
263 % \node[state, accepting] (q2) at ( 2,1) {$q_2$}; |
|
264 % \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) |
|
265 % (q1) edge[bend left] node[above] {\alert{$b$}} (q0) |
|
266 % (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) |
|
267 % (q1) edge node[above] {\alert{$a$}} (q2) |
|
268 % (q2) edge [loop right] node {\alert{$a$}} () |
|
269 % (q0) edge [loop below] node {\alert{$b$}} (); |
|
270 % \end{tikzpicture} |
|
271 % \end{center}\bigskip |
|
272 |
|
273 % \begin{center} |
|
274 % \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l} |
|
275 % \bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b + q_2\,b$} & (start state)\\ |
|
276 % \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ |
|
277 % \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ |
|
278 |
|
279 % \end{tabular} |
|
280 % \end{center} |
|
281 |
|
282 % Arden's Lemma: |
|
283 % \begin{center} |
|
284 % If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} |
|
285 % \end{center} |
|
286 |
|
287 |
|
288 % \end{frame} |
|
289 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
290 |
|
291 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
292 % \begin{frame}[c] |
|
293 % \frametitle{DFA Minimisation} |
|
294 |
|
295 % \begin{enumerate} |
|
296 % \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$} |
|
297 % \item Mark all pairs that accepting and non-accepting states |
|
298 % \item For all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether |
|
299 % \begin{center} |
|
300 % \bl{$(\delta(q, c), \delta(p,c))$} |
|
301 % \end{center} |
|
302 % are marked. If yes, then also mark \bl{$(q, p)$}. |
|
303 % \item Repeat last step until no change. |
|
304 % \item All unmarked pairs can be merged. |
|
305 % \end{enumerate} |
|
306 |
|
307 % \end{frame} |
|
308 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
309 |
|
310 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
311 % \begin{frame}[c] |
|
312 |
|
313 % \begin{center} |
|
314 % \begin{tabular}{@{\hspace{-8mm}}cc@{}} |
|
315 % \begin{tikzpicture}[>=stealth',very thick,auto, |
|
316 % every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
|
317 % \node[state,initial] (q_0) {$q_0$}; |
|
318 % \node[state] (q_1) [right=of q_0] {$q_1$}; |
|
319 % \node[state] (q_2) [below right=of q_0] {$q_2$}; |
|
320 % \node[state] (q_3) [right=of q_2] {$q_3$}; |
|
321 % \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; |
|
322 % \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); |
|
323 % \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); |
|
324 % \path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); |
|
325 % \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); |
|
326 % \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); |
|
327 % \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
|
328 % \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
|
329 % \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
|
330 % \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); |
|
331 % \end{tikzpicture} |
|
332 % & |
|
333 % \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm] |
|
334 % \draw (0,0) -- (4,0); |
|
335 % \draw (0,1) -- (4,1); |
|
336 % \draw (0,2) -- (3,2); |
|
337 % \draw (0,3) -- (2,3); |
|
338 % \draw (0,4) -- (1,4); |
|
339 |
|
340 % \draw (0,0) -- (0, 4); |
|
341 % \draw (1,0) -- (1, 4); |
|
342 % \draw (2,0) -- (2, 3); |
|
343 % \draw (3,0) -- (3, 2); |
|
344 % \draw (4,0) -- (4, 1); |
|
345 |
|
346 % \draw (0.5,-0.5) node {$q_0$}; |
|
347 % \draw (1.5,-0.5) node {$q_1$}; |
|
348 % \draw (2.5,-0.5) node {$q_2$}; |
|
349 % \draw (3.5,-0.5) node {$q_3$}; |
|
350 |
|
351 % \draw (-0.5, 3.5) node {$q_1$}; |
|
352 % \draw (-0.5, 2.5) node {$q_2$}; |
|
353 % \draw (-0.5, 1.5) node {$q_3$}; |
|
354 % \draw (-0.5, 0.5) node {$q_4$}; |
|
355 |
|
356 % \draw (0.5,0.5) node {\large$\star$}; |
|
357 % \draw (1.5,0.5) node {\large$\star$}; |
|
358 % \draw (2.5,0.5) node {\large$\star$}; |
|
359 % \draw (3.5,0.5) node {\large$\star$}; |
|
360 % \draw (0.5,1.5) node {\large$\star$}; |
|
361 % \draw (2.5,1.5) node {\large$\star$}; |
|
362 % \draw (0.5,3.5) node {\large$\star$}; |
|
363 % \draw (1.5,2.5) node {\large$\star$}; |
|
364 % \end{tikzpicture}} |
|
365 % \end{tabular} |
|
366 % \end{center} |
|
367 |
|
368 |
|
369 % \mbox{}\\[-20mm]\mbox{} |
|
370 |
|
371 % \begin{center} |
|
372 % \begin{tikzpicture}[>=stealth',very thick,auto, |
|
373 % every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
|
374 % \node[state,initial] (q_02) {$q_{0, 2}$}; |
|
375 % \node[state] (q_13) [right=of q_02] {$q_{1, 3}$}; |
|
376 % \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$}; |
|
377 % \path[->] (q_02) edge [bend left] node [above] {\alert{$a$}} (q_13); |
|
378 % \path[->] (q_13) edge [bend left] node [below] {\alert{$b$}} (q_02); |
|
379 % \path[->] (q_02) edge [loop below] node {\alert{$b$}} (); |
|
380 % \path[->] (q_13) edge node [above] {\alert{$a$}} (q_4); |
|
381 % \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); |
|
382 % \end{tikzpicture}\\ |
|
383 % minimal automaton |
|
384 % \end{center} |
|
385 |
|
386 % \end{frame} |
|
387 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
388 |
|
389 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
390 \begin{frame}[c] |
|
391 \frametitle{Regular Languages} |
|
392 |
|
393 Two equivalent definitions:\bigskip |
|
394 |
|
395 \begin{quote}\rm A language is \alert{regular} iff there exists a |
|
396 regular expression that recognises all its strings. |
|
397 \end{quote} |
|
398 |
|
399 \begin{quote}\rm A language is \alert{regular} iff there exists an |
|
400 automaton that recognises all its strings. |
|
401 \end{quote}\bigskip\bigskip |
|
402 |
|
403 |
|
404 \small |
|
405 for example \bl{$a^nb^n$} is not regular |
|
406 \end{frame} |
|
407 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
408 |
|
409 |
|
410 |
|
411 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
412 \begin{frame}[c] |
|
413 \frametitle{Negation} |
|
414 |
|
415 Regular languages are closed under negation:\bigskip |
|
416 |
|
417 \begin{center} |
|
418 \begin{tikzpicture}[scale=2,>=stealth',very thick, |
|
419 every state/.style={minimum size=0pt, |
|
420 draw=blue!50,very thick,fill=blue!20}] |
|
421 \only<1>{\node[state,initial] (q0) at ( 0,1) {$q_0$};} |
|
422 \only<2>{\node[state,initial,accepting] (q0) at ( 0,1) {$q_0$};} |
|
423 \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
424 \only<2>{\node[state,accepting] (q1) at ( 1,1) {$q_1$};} |
|
425 \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};} |
|
426 \only<2>{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
427 \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) |
|
428 (q1) edge[bend left] node[above] {\alert{$b$}} (q0) |
|
429 (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) |
|
430 (q1) edge node[above] {\alert{$a$}} (q2) |
|
431 (q2) edge [loop right] node {\alert{$a$}} () |
|
432 (q0) edge [loop below] node {\alert{$b$}} (); |
|
433 \end{tikzpicture} |
|
434 \end{center}\bigskip\bigskip |
|
435 |
|
436 But requires that the automaton is \alert{completed}! |
|
437 |
|
438 \end{frame} |
|
439 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
440 |
108 |
441 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
109 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
442 \begin{frame}[c] |
110 \begin{frame}[c] |
443 \frametitle{The Goal of this Course} |
111 \frametitle{The Goal of this Course} |
444 \mbox{}\\[-26mm]\mbox{} |
112 \mbox{}\\[-26mm]\mbox{} |
1472 |
1140 |
1473 \end{frame} |
1141 \end{frame} |
1474 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1142 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1475 |
1143 |
1476 |
1144 |
|
1145 |
|
1146 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1147 \begin{frame}[c] |
|
1148 \frametitle{\begin{tabular}{c}Last Week\\[-2mm] |
|
1149 Regexes and Values\end{tabular}} |
|
1150 |
|
1151 Regular expressions and their corresponding values: |
|
1152 |
|
1153 \begin{center} |
|
1154 \begin{columns} |
|
1155 \begin{column}{3cm} |
|
1156 \begin{tabular}{@{}rrl@{}} |
|
1157 \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$}\\ |
|
1158 & \bl{$\mid$} & \bl{$\ONE$} \\ |
|
1159 & \bl{$\mid$} & \bl{$c$} \\ |
|
1160 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\ |
|
1161 & \bl{$\mid$} & \bl{$r_1 + r_2$} \\ |
|
1162 \\ |
|
1163 & \bl{$\mid$} & \bl{$r^*$} \\ |
|
1164 \end{tabular} |
|
1165 \end{column} |
|
1166 \begin{column}{3cm} |
|
1167 \begin{tabular}{@{\hspace{-7mm}}rrl@{}} |
|
1168 \bl{$v$} & \bl{$::=$} & \\ |
|
1169 & & \bl{$Empty$} \\ |
|
1170 & \bl{$\mid$} & \bl{$Char(c)$} \\ |
|
1171 & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\ |
|
1172 & \bl{$\mid$} & \bl{$Left(v)$} \\ |
|
1173 & \bl{$\mid$} & \bl{$Right(v)$} \\ |
|
1174 & \bl{$\mid$} & \bl{$Stars [v_1,\ldots\,v_n]$} \\ |
|
1175 \end{tabular} |
|
1176 \end{column} |
|
1177 \end{columns} |
|
1178 \end{center} |
|
1179 |
|
1180 |
|
1181 \end{frame} |
|
1182 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1183 |
|
1184 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1185 \begin{frame}[c] |
|
1186 |
|
1187 \begin{textblock}{10}(3,5) |
|
1188 \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] |
|
1189 \node (r1) {\bl{$r_1$}}; |
|
1190 \node (r2) [right=of r1] {\bl{$r_2$}}; |
|
1191 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}}; |
|
1192 \node (r3) [right=of r2] {\bl{$r_3$}}; |
|
1193 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}}; |
|
1194 \node (r4) [right=of r3] {\bl{$r_4$}}; |
|
1195 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}}; |
|
1196 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}}; |
|
1197 \node (v4) [below=of r4] {\bl{$v_4$}}; |
|
1198 \draw[->,line width=1mm] (r4) -- (v4); |
|
1199 \node (v3) [left=of v4] {\bl{$v_3$}}; |
|
1200 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}}; |
|
1201 \node (v2) [left=of v3] {\bl{$v_2$}}; |
|
1202 \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}}; |
|
1203 \node (v1) [left=of v2] {\bl{$v_1$}}; |
|
1204 \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}}; |
|
1205 \draw[->,line width=0.5mm] (r3) -- (v3); |
|
1206 \draw[->,line width=0.5mm] (r2) -- (v2); |
|
1207 \draw[->,line width=0.5mm] (r1) -- (v1); |
|
1208 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; |
|
1209 \end{tikzpicture} |
|
1210 \end{textblock} |
|
1211 |
|
1212 \begin{textblock}{6}(1,0.8) |
|
1213 \begin{bubble}[6cm] |
|
1214 \small |
|
1215 \begin{tabular}{ll} |
|
1216 \bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\ |
|
1217 \bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\ |
|
1218 \bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\ |
|
1219 \bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\ |
|
1220 \end{tabular} |
|
1221 \end{bubble} |
|
1222 \end{textblock} |
|
1223 |
|
1224 \begin{textblock}{6}(1,11.4) |
|
1225 \begin{bubble}[7.6cm] |
|
1226 \small |
|
1227 \begin{tabular}{ll} |
|
1228 \bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\ |
|
1229 \bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\ |
|
1230 \bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\ |
|
1231 \bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\ |
|
1232 \end{tabular} |
|
1233 \end{bubble} |
|
1234 \end{textblock} |
|
1235 |
|
1236 \begin{textblock}{6}(12,11.4) |
|
1237 \begin{bubble}[2cm] |
|
1238 \small |
|
1239 \begin{tabular}{ll} |
|
1240 \bl{$|v_1|$}: & \bl{$abc$}\\ |
|
1241 \bl{$|v_2|$}: & \bl{$bc$}\\ |
|
1242 \bl{$|v_3|$}: & \bl{$c$}\\ |
|
1243 \bl{$|v_4|$}: & \bl{$[]$} |
|
1244 \end{tabular} |
|
1245 \end{bubble} |
|
1246 \end{textblock} |
|
1247 |
|
1248 |
|
1249 \end{frame} |
|
1250 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1251 |
|
1252 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1253 \begin{frame}[c] |
|
1254 \frametitle{Simplification} |
|
1255 |
|
1256 \begin{itemize} |
|
1257 \item If we simplify after the derivative, then we are builing the |
|
1258 value for the simplified regular expression, but \emph{not} for the original |
|
1259 regular expression. |
|
1260 \end{itemize} |
|
1261 |
|
1262 \begin{center} |
|
1263 \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] |
|
1264 \node (r1) {\bl{$r_1$}}; |
|
1265 \node (r2) [right=of r1] {\bl{$r_2$}}; |
|
1266 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}}; |
|
1267 \node (r3) [right=of r2] {\bl{$r_3$}}; |
|
1268 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}}; |
|
1269 \node (r4) [right=of r3] {\bl{$r_4$}}; |
|
1270 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}}; |
|
1271 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}}; |
|
1272 \node (v4) [below=of r4] {\bl{$v_4$}}; |
|
1273 \draw[->,line width=1mm] (r4) -- (v4); |
|
1274 \node (v3) [left=of v4] {\bl{$v_3$}}; |
|
1275 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}}; |
|
1276 \node (v2) [left=of v3] {\bl{$v_2$}}; |
|
1277 \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}}; |
|
1278 \node (v1) [left=of v2] {\bl{$v_1$}}; |
|
1279 \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}}; |
|
1280 \draw[->,line width=0.5mm] (r3) -- (v3); |
|
1281 \draw[->,line width=0.5mm] (r2) -- (v2); |
|
1282 \draw[->,line width=0.5mm] (r1) -- (v1); |
|
1283 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; |
|
1284 \end{tikzpicture} |
|
1285 \end{center} |
|
1286 |
|
1287 \small |
|
1288 \hspace{4.5cm}\bl{$(b \cdot c) + (\ZERO + \ONE)$} |
|
1289 $\mapsto$ |
|
1290 \bl{$(b \cdot c) + \ONE$} |
|
1291 |
|
1292 \end{frame} |
|
1293 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1294 |
|
1295 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1296 % \begin{frame}[t] |
|
1297 |
|
1298 % \begin{center} |
|
1299 % \bl{$\only<1>{(b \cdot c)}% |
|
1300 % \only<2-3>{(\underline{b \cdot c})}% |
|
1301 % \only<1-3>{+}% |
|
1302 % \only<1>{(\ZERO + \ONE)}% |
|
1303 % \only<2-3>{(\underline{\ZERO + \ONE})}$}% |
|
1304 % \only<4->{% |
|
1305 % \bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}% |
|
1306 % } |
|
1307 % $\mapsto$ |
|
1308 % \bl{$(b \cdot c) + \ONE$} |
|
1309 % \end{center}\bigskip |
|
1310 |
|
1311 % \onslide<3->{% |
|
1312 % \begin{center} |
|
1313 % \begin{tabular}{lcl} |
|
1314 % \bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\ |
|
1315 % \bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$} |
|
1316 % \end{tabular} |
|
1317 % \end{center}} |
|
1318 |
|
1319 % \only<4>{% |
|
1320 % \begin{center} |
|
1321 % \begin{tabular}{@{}l@{\hspace{1mm}}l@{}} |
|
1322 % \bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\ |
|
1323 % \quad \bl{$\lambda v.\,$} |
|
1324 % case \bl{$v = Left(v')$}: |
|
1325 % & return \bl{$Left(f_{s1}(v'))$}\\ |
|
1326 % \quad \phantom{$\lambda v.\,$} |
|
1327 % case \bl{$v = Right(v')$}: |
|
1328 % & return \bl{$Right(f_{s2}(v'))$}\\ |
|
1329 % \end{tabular} |
|
1330 % \end{center}}% |
|
1331 % \only<5->{% |
|
1332 % \begin{center} |
|
1333 % \begin{tabular}{@{}l@{\hspace{1mm}}l@{}} |
|
1334 % \only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\ |
|
1335 % \quad \bl{$\lambda v.\,$} |
|
1336 % case \bl{$v = Left(v')$}: |
|
1337 % & return \bl{$Left(v')$}\\ |
|
1338 % \quad \phantom{$\lambda v.\,$} |
|
1339 % case \bl{$v = Right(v')$}: |
|
1340 % & return \bl{$Right(Right(v'))$}\\ |
|
1341 % \end{tabular} |
|
1342 % \end{center}}% |
|
1343 |
|
1344 % \only<6->{% |
|
1345 % \begin{center} |
|
1346 % \begin{tabular}{@{}l@{\hspace{4mm}}l@{}} |
|
1347 % \bl{$\textit{mkeps}$} simplified case: & |
|
1348 % \bl{$\textit{Right}(\textit{Empty})$}\\ |
|
1349 % rectified case: & |
|
1350 % \bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$} |
|
1351 % \end{tabular} |
|
1352 % \end{center}}% |
|
1353 |
|
1354 % \end{frame} |
|
1355 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1356 |
|
1357 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1358 \begin{frame}[c] |
|
1359 \frametitle{Records} |
|
1360 |
|
1361 \begin{itemize} |
|
1362 \item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause |
|
1363 |
|
1364 \item \bl{$nullable(x:r) \dn nullable(r)$} |
|
1365 \item \bl{$der\,c\,(x:r) \dn der\,c\,r$} |
|
1366 \item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$} |
|
1367 \item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$} |
|
1368 \end{itemize}\bigskip\bigskip\pause |
|
1369 |
|
1370 \small |
|
1371 for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$} |
|
1372 |
|
1373 \end{frame} |
|
1374 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1375 |
|
1376 |
|
1377 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1378 \begin{frame}[c] |
|
1379 \frametitle{Environments} |
|
1380 |
|
1381 Obtaining the ``recorded'' parts of a value: |
|
1382 |
|
1383 \begin{center} |
|
1384 \begin{tabular}{lcl} |
|
1385 \bl{$env(Empty)$} & \bl{$\dn$} & \bl{$[]$}\\ |
|
1386 \bl{$env(Char(c))$} & \bl{$\dn$} & \bl{$[]$}\\ |
|
1387 \bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\ |
|
1388 \bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\ |
|
1389 \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\ |
|
1390 \bl{$env(Stars [v_1,\ldots ,v_n])$} & \bl{$\dn$} & |
|
1391 \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\ |
|
1392 \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\ |
|
1393 \end{tabular} |
|
1394 \end{center} |
|
1395 |
|
1396 \end{frame} |
|
1397 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1398 |
|
1399 |
|
1400 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1401 \begin{frame}[c] |
|
1402 \frametitle{While Tokens} |
|
1403 |
|
1404 \begin{center} |
|
1405 \begin{tabular}{@{}r@{\hspace{2mm}}c@{\hspace{2mm}}l@{}} |
|
1406 \pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\ |
|
1407 & & \phantom{(}\pcode{("i" : ID)} +\\ |
|
1408 & & \phantom{(}\pcode{("o" : OP)} + \\ |
|
1409 & & \phantom{(}\pcode{("n" : NUM)} + \\ |
|
1410 & & \phantom{(}\pcode{("s" : SEMI)} +\\ |
|
1411 & & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\ |
|
1412 & & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\ |
|
1413 & & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$} |
|
1414 \end{tabular} |
|
1415 \end{center} |
|
1416 |
|
1417 \end{frame} |
|
1418 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1419 |
|
1420 |
|
1421 |
|
1422 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1423 \begin{frame}[t] |
|
1424 |
|
1425 \consolas |
|
1426 \begin{center} |
|
1427 \code{"if true then then 42 else +"} |
|
1428 \end{center} |
|
1429 |
|
1430 \only<1>{ |
|
1431 \small\begin{tabular}{l} |
|
1432 KEYWORD(if),\\ |
|
1433 WHITESPACE,\\ |
|
1434 IDENT(true),\\ |
|
1435 WHITESPACE,\\ |
|
1436 KEYWORD(then),\\ |
|
1437 WHITESPACE,\\ |
|
1438 KEYWORD(then),\\ |
|
1439 WHITESPACE,\\ |
|
1440 NUM(42),\\ |
|
1441 WHITESPACE,\\ |
|
1442 KEYWORD(else),\\ |
|
1443 WHITESPACE,\\ |
|
1444 OP(+) |
|
1445 \end{tabular}} |
|
1446 |
|
1447 \only<2>{ |
|
1448 \small\begin{tabular}{l} |
|
1449 KEYWORD(if),\\ |
|
1450 IDENT(true),\\ |
|
1451 KEYWORD(then),\\ |
|
1452 KEYWORD(then),\\ |
|
1453 NUM(42),\\ |
|
1454 KEYWORD(else),\\ |
|
1455 OP(+) |
|
1456 \end{tabular}} |
|
1457 |
|
1458 \end{frame} |
|
1459 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1460 |
|
1461 |
|
1462 |
|
1463 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1464 %\begin{frame}[c] |
|
1465 %\frametitle{Coursework: PLs (16)} |
|
1466 % |
|
1467 %\begin{itemize} |
|
1468 %\item Java (16) |
|
1469 %\item C++, C, C\# (14) |
|
1470 %\item JavaScript (10) |
|
1471 %\item Scala (9) |
|
1472 %\item Python (9) |
|
1473 %\item PHP (6) |
|
1474 %\item Haskell (3) |
|
1475 %\item Ruby (4) |
|
1476 %\item Bash, Perl, Powershell (2) |
|
1477 %\item TypeScript (1) |
|
1478 %\item R (1) |
|
1479 %\item Coconut (1) |
|
1480 %\item Pascal (1) |
|
1481 %\end{itemize} |
|
1482 % |
|
1483 %\end{frame} |
|
1484 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1485 |
|
1486 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1487 %\begin{frame}[c] |
|
1488 %\frametitle{Coursework: Nullable} |
|
1489 % |
|
1490 %\begin{center} |
|
1491 %\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
|
1492 % \bl{$nullable([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\ |
|
1493 % \bl{$nullable(r^+)$} & \bl{$\dn$} & $?$\\ |
|
1494 % \bl{$nullable(r^?)$} & \bl{$\dn$} & $?$\\ |
|
1495 % \bl{$nullable(r^{\{n\}})$} & \bl{$\dn$} & $?$\\ |
|
1496 % \bl{$nullable(r^{\{n..\}})$} & \bl{$\dn$} & $?$\\ |
|
1497 % \bl{$nullable(r^{\{..n\}})$} & \bl{$\dn$} & $?$\\ |
|
1498 % \bl{$nullable(r^{\{n..m\}})$} & \bl{$\dn$} & $?$\\ |
|
1499 % \bl{$nullable(\sim{}r)$} & \bl{$\dn$} & $?$\\ |
|
1500 % |
|
1501 %\end{tabular} |
|
1502 %\end{center} |
|
1503 % |
|
1504 %\end{frame} |
|
1505 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1506 |
|
1507 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1508 %\begin{frame}[c] |
|
1509 %%%\frametitle{Coursework: der} |
|
1510 % |
|
1511 %\begin{center} |
|
1512 %\begin{tabular}{@ {}l@ {\hspace{1mm}}c@ {\hspace{1mm}}l@ {}} |
|
1513 % \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\ |
|
1514 % \bl{$der\, c\, (r^+)$} & \bl{$\dn$} & $?$\\ |
|
1515 % \bl{$der\, c\, (r^?)$} & \bl{$\dn$} & $?$\\ |
|
1516 % \bl{$der\, c\, (r^{\{n\}})$} & \bl{$\dn$} & |
|
1517 % \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-\liningnums{1}\}}$}\\ |
|
1518 % \bl{$der\, c\, (r^{\{n..\}})$} & \bl{$\dn$} & |
|
1519 % \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\ |
|
1520 % & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..\}}$}\\ |
|
1521 % \bl{$der\, c\, (r^{\{..n\}})$} & \bl{$\dn$} & |
|
1522 % \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-\liningnums{1}\}}$}\\ |
|
1523 % |
|
1524 % \bl{$der\, c\, (r^{\{n..m\}})$} & \bl{$\dn$} & |
|
1525 % \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\ |
|
1526 % \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-\liningnums{1}\}}$}}\\ |
|
1527 % \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else |
|
1528 % \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..m-\liningnums{1}\}}$}}\\ |
|
1529 % \bl{$der\, c\, (\sim{}r)$} & \bl{$\dn$} & $?$\\ |
|
1530 %\end{tabular} |
|
1531 %\end{center} |
|
1532 % |
|
1533 %\end{frame} |
|
1534 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1535 |
|
1536 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1537 %\begin{frame}[c] |
|
1538 %\frametitle{Coursework: CFUN} |
|
1539 % |
|
1540 %\begin{center} |
|
1541 %\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
|
1542 % \bl{$nullable(CFUN(\_))$} & \bl{$\dn$} & \bl{$false$}\\ |
|
1543 % \bl{$der\,c\,(CFUN(f))$} & \bl{$\dn$} & |
|
1544 % \bl{$if\;f(c)\;then\;\ONE\;else\;\ZERO$}\bigskip\\ |
|
1545 % \bl{$CHAR(c)$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;c=d)$}\\ |
|
1546 % \bl{$CSET([c_1,\ldots,c_n])$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;d\in [c_1,\ldots,c_n])$}\\ |
|
1547 % \bl{$ALL$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;true)$}\\ |
|
1548 %\end{tabular} |
|
1549 %\end{center} |
|
1550 % |
|
1551 %\end{frame} |
|
1552 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1553 |
|
1554 |
1477 \end{document} |
1555 \end{document} |
1478 |
1556 |
1479 %%% Local Variables: |
1557 %%% Local Variables: |
1480 %%% mode: latex |
1558 %%% mode: latex |
1481 %%% TeX-master: t |
1559 %%% TeX-master: t |