27 \begin{frame}[t] |
27 \begin{frame}[t] |
28 \frametitle{% |
28 \frametitle{% |
29 \begin{tabular}{@ {}c@ {}} |
29 \begin{tabular}{@ {}c@ {}} |
30 \\[-3mm] |
30 \\[-3mm] |
31 \LARGE Compilers and \\[-1mm] |
31 \LARGE Compilers and \\[-1mm] |
32 \LARGE Formal Languages (2)\\[3mm] |
32 \LARGE Formal Languages\\[3mm] |
33 \end{tabular}} |
33 \end{tabular}} |
34 |
34 |
35 \normalsize |
35 \normalsize |
36 \begin{center} |
36 \begin{center} |
37 \begin{tabular}{ll} |
37 \begin{tabular}{ll} |
38 Email: & christian.urban at kcl.ac.uk\\ |
38 Email: & christian.urban at kcl.ac.uk\\ |
39 Office Hours: & Thursdays 12 -- 14\\ |
39 %Office Hours: & Thursdays 12 -- 14\\ |
40 Location: & N7.07 (North Wing, Bush House)\\ |
40 %Location: & N7.07 (North Wing, Bush House)\\ |
41 Slides \& Progs: & KEATS (also homework is there)\\ |
41 Slides \& Progs: & KEATS (also homework is there)\\ |
42 \end{tabular} |
42 \end{tabular} |
43 \end{center} |
43 \end{center} |
44 |
44 |
|
45 \begin{center} |
|
46 \begin{tikzpicture} |
|
47 \node[drop shadow,fill=white,inner sep=0pt] |
|
48 {\footnotesize\rowcolors{1}{capri!10}{white} |
|
49 \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline |
|
50 1 Introduction, Languages & 6 While-Language \\ |
|
51 \cellcolor{blue!50} |
|
52 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\ |
|
53 3 Automata, Regular Languages & 8 Compiling Functional Languages \\ |
|
54 4 Lexing, Tokenising & 9 Optimisations \\ |
|
55 5 Grammars, Parsing & 10 LLVM \\ \hline |
|
56 \end{tabular}% |
|
57 }; |
|
58 \end{tikzpicture} |
|
59 \end{center} |
|
60 |
45 \end{frame} |
61 \end{frame} |
46 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
62 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
47 |
63 |
48 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
64 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
49 \begin{frame}[t] |
65 \begin{frame}[t] |
50 \frametitle{ |
66 \frametitle{ |
51 Lets Implement an Efficient\\[-2mm] |
67 Let's Implement an Efficient\\[-2mm] |
52 Regular Expression Matcher} |
68 Regular Expression Matcher} |
53 |
69 |
54 \footnotesize |
70 \footnotesize |
55 \begin{center} |
71 \begin{center} |
56 {\normalsize Graphs: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$} and strings \bl{$\underbrace{\,a\ldots a\,}_{n}$}}\medskip\\ |
72 {\normalsize Graphs: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$} and strings \bl{$\underbrace{\,a\ldots a\,}_{n}$}}\medskip\\ |
147 & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\ |
163 & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\ |
148 \end{tabular} |
164 \end{tabular} |
149 \end{center} |
165 \end{center} |
150 \vspace{\fill} |
166 \vspace{\fill} |
151 |
167 |
152 Q: \;What about \;\bl{$r \cdot 0$} \; ? |
168 %%Q: \;What about \;\bl{$r \cdot 0$} \; ? |
153 \end{frame} |
|
154 |
|
155 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
156 \begin{frame}[c] |
|
157 \frametitle{Languages (Sets of Strings)} |
|
158 |
|
159 \begin{itemize} |
|
160 |
|
161 \item A \alert{\bf Language} is a set of strings, for example\medskip |
|
162 \begin{center} |
|
163 \bl{$\{[], hello, foobar, a, abc\}$} |
|
164 \end{center}\bigskip |
|
165 |
|
166 \item \alert{\bf Concatenation} for strings and languages |
|
167 |
|
168 \begin{center} |
|
169 \begin{tabular}{rcl} |
|
170 \bl{$foo\;@\;bar$} & \bl{$=$} & \bl{$foobar$}\medskip\\ |
|
171 \bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$} |
|
172 \end{tabular} |
|
173 \end{center} |
|
174 \bigskip |
|
175 |
|
176 \small |
|
177 \item [] For example \bl{$A = \{foo, bar\}$}, \bl{$B = \{a, b\}$} |
|
178 |
|
179 \[ |
|
180 \bl{A \,@\, B = \{fooa, foob, bara, barb\}} |
|
181 \] |
|
182 |
|
183 \end{itemize} |
|
184 \end{frame} |
|
185 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
186 |
|
187 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
188 \begin{frame}[c] |
|
189 \frametitle{Two Corner Cases} |
|
190 |
|
191 \Large |
|
192 \begin{center} |
|
193 \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\ |
|
194 \bl{$A \,@\, \{\} = \;?$} |
|
195 \end{center} |
|
196 |
|
197 \end{frame} |
|
198 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
199 |
|
200 |
|
201 |
|
202 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
203 \begin{frame}[c] |
|
204 \frametitle{ |
|
205 The Meaning of a\\[-2mm] |
|
206 Regular Expression} |
|
207 |
|
208 ...all the strings a regular expression can match. |
|
209 |
|
210 \begin{center} |
|
211 \begin{tabular}{rcl} |
|
212 \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ |
|
213 \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
|
214 \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ |
|
215 \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ |
|
216 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ |
|
217 \bl{$L(r^*)$} & \bl{$\dn$} & \\ |
|
218 \end{tabular} |
|
219 \end{center} |
|
220 |
|
221 \begin{textblock}{14}(1.5,13.5)\small |
|
222 \bl{$L$} is a function from regular expressions to |
|
223 sets of strings (languages):\smallskip\\ |
|
224 \bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
|
225 \end{textblock} |
|
226 |
|
227 \end{frame} |
|
228 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
229 |
|
230 |
|
231 |
|
232 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
233 \begin{frame}[c] |
|
234 \frametitle{The Power Operation} |
|
235 |
|
236 \begin{itemize} |
|
237 \item The \alert{\textbf{\boldmath$n$th Power}} of a language: |
|
238 |
|
239 \begin{center} |
|
240 \begin{tabular}{lcl} |
|
241 \bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
|
242 \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$} |
|
243 \end{tabular} |
|
244 \end{center}\bigskip |
|
245 |
|
246 \item[] For example |
|
247 |
|
248 \begin{center} |
|
249 \begin{tabular}{lcl@{\hspace{10mm}}l} |
|
250 \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\ |
|
251 \bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\ |
|
252 \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\ |
|
253 \end{tabular} |
|
254 \end{center} |
|
255 |
|
256 \end{itemize} |
|
257 |
|
258 \end{frame} |
|
259 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
260 |
|
261 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
262 \begin{frame}[c] |
|
263 \frametitle{Homework Question} |
|
264 |
|
265 \begin{itemize} |
|
266 \item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip |
|
267 |
|
268 \item[] |
|
269 How many strings are in \bl{$A^4$}\,? |
|
270 \bigskip\medskip\pause |
|
271 |
|
272 |
|
273 \item[] |
|
274 What if \bl{$A = \{[a],[b],[c],[]\}$};\\ |
|
275 how many strings are then in \bl{$A^4$}\,? |
|
276 \end{itemize} |
|
277 |
|
278 \end{frame} |
|
279 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
280 |
|
281 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
282 \begin{frame}[c] |
|
283 \frametitle{The Star Operation} |
|
284 |
|
285 \begin{itemize} |
|
286 \item The \alert{\bf Kleene Star} of a \underline{language}: |
|
287 \bigskip |
|
288 |
|
289 \begin{center} |
|
290 \begin{tabular}{c} |
|
291 \bl{$A\star \dn \bigcup_{0\le n} A^n$} |
|
292 \end{tabular} |
|
293 \end{center}\bigskip |
|
294 |
|
295 \item[] This expands to |
|
296 |
|
297 \[ |
|
298 \bl{A^0 \cup A^1 \cup A^2 \cup A^3 \cup A^4 \cup \ldots} |
|
299 \] |
|
300 |
|
301 or |
|
302 |
|
303 \small |
|
304 \[ |
|
305 \bl{\{[]\} \;\cup\; A \;\cup\; A\,@\,A \;\cup\; |
|
306 A\,@\,A\,@\,A \;\cup\; A\,@\,A\,@\,A\,@\,A \cup \ldots} |
|
307 \] |
|
308 |
|
309 \end{itemize} |
|
310 |
|
311 \end{frame} |
|
312 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
313 |
|
314 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
315 \begin{frame}[c] |
|
316 \frametitle{ |
|
317 The Meaning of a\\[-2mm] |
|
318 Regular Expression} |
|
319 |
|
320 ...all the strings a regular expression can match. |
|
321 |
|
322 \begin{center} |
|
323 \begin{tabular}{rcl} |
|
324 \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ |
|
325 \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
|
326 \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ |
|
327 \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ |
|
328 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ |
|
329 \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star \quad\dn \bigcup_{0 \le n} L(r)^n$}\\ |
|
330 \end{tabular} |
|
331 \end{center} |
|
332 |
|
333 %\begin{textblock}{9}(6,12)\small |
|
334 %\bl{$L$} is a function from regular expressions to |
|
335 %sets of strings (languages):\smallskip\\ |
|
336 %\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
|
337 %\end{textblock} |
|
338 |
|
339 \end{frame} |
169 \end{frame} |
340 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
170 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
341 |
171 |
342 |
172 |
343 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
173 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1218 not allowed to contain \bl{$\_ + \_$}\/? |
1035 not allowed to contain \bl{$\_ + \_$}\/? |
1219 \end{itemize} |
1036 \end{itemize} |
1220 |
1037 |
1221 \end{frame} |
1038 \end{frame} |
1222 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1039 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1223 |
1040 |
|
1041 |
|
1042 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1043 \begin{frame}[c] |
|
1044 \frametitle{\begin{tabular}{c}\\[3cm]\huge\alert{Questions?}\end{tabular}} |
|
1045 |
|
1046 \bigskip |
|
1047 homework (written exam 80\%)\\ |
|
1048 coursework (20\%; first one today)\\ |
|
1049 submission Fridays @ 18:00 -- accepted until Mondays |
|
1050 \mbox{} |
|
1051 \end{frame} |
|
1052 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1053 |
|
1054 |
|
1055 |
|
1056 |
|
1057 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1058 \begin{frame}[c] |
|
1059 \frametitle{Last Week} |
|
1060 |
|
1061 Last week I showed you a regular expression matcher |
|
1062 that works provably correct in all cases (we only |
|
1063 started with the proving part though) |
|
1064 |
|
1065 \begin{center} |
|
1066 \bl{$matches\,s\,r$} \;\;if and only if \;\; \bl{$s \in L(r)$} |
|
1067 \end{center}\bigskip\bigskip |
|
1068 |
|
1069 \small |
|
1070 \textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)} |
|
1071 |
|
1072 \end{frame} |
|
1073 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1074 |
|
1075 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1076 \begin{frame}[c] |
|
1077 \frametitle{The Derivative of a Rexp} |
|
1078 |
|
1079 \begin{center} |
|
1080 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
|
1081 \bl{$der\, c\, (\ZERO)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\ |
|
1082 \bl{$der\, c\, (\ONE)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\ |
|
1083 \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\ |
|
1084 \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\ |
|
1085 \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ |
|
1086 & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ |
|
1087 & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\ |
|
1088 \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\ |
|
1089 |
|
1090 \bl{$\textit{ders}\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ |
|
1091 \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\ |
|
1092 \end{tabular} |
|
1093 \end{center} |
|
1094 |
|
1095 \end{frame} |
|
1096 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1097 |
|
1098 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1099 \begin{frame}[c] |
|
1100 \frametitle{Example} |
|
1101 |
|
1102 Given \bl{$r \dn ((a \cdot b) + b)^*$} what is |
|
1103 |
|
1104 \begin{center} |
|
1105 \def\arraystretch{1.5} |
|
1106 \begin{tabular}{@{}lcl} |
|
1107 \bl{$\der\,a\,((a \cdot b) + b)^*$} |
|
1108 & \bl{$\Rightarrow$}& \bl{$\der\,a\, \underline{((a \cdot b) + b)^*}$}\\ |
|
1109 & \bl{$=$} & \bl{$(der\,a\,(\underline{(a \cdot b) + b})) \cdot r$}\\ |
|
1110 & \bl{$=$} & \bl{$((der\,a\,(\underline{a \cdot b})) + (der\,a\,b)) \cdot r$}\\ |
|
1111 & \bl{$=$} & \bl{$(((der\,a\,\underline{a}) \cdot b) + (der\,a\,b)) \cdot r$}\\ |
|
1112 & \bl{$=$} & \bl{$((\ONE \cdot b) + (der\,a\,\underline{b})) \cdot r$}\\ |
|
1113 & \bl{$=$} & \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}\\ |
|
1114 \end{tabular} |
|
1115 \end{center} |
|
1116 |
|
1117 \end{frame} |
|
1118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1119 |
|
1120 |
|
1121 |
|
1122 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1123 \begin{frame}[c] |
|
1124 |
|
1125 Input: string \bl{$abc$} and regular expression \bl{$r$} |
|
1126 |
|
1127 \begin{enumerate} |
|
1128 \item \bl{$der\,a\,r$} |
|
1129 \item \bl{$der\,b\,(der\,a\,r)$} |
|
1130 \item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause |
|
1131 \item finally check whether the last regular expression can match the empty string |
|
1132 \end{enumerate} |
|
1133 |
|
1134 \end{frame} |
|
1135 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1136 |
|
1137 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1138 \begin{frame}[t] |
|
1139 \frametitle{Simplification} |
|
1140 |
|
1141 Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows |
|
1142 |
|
1143 \begin{center} |
|
1144 \def\arraystretch{2} |
|
1145 \begin{tabular}{@{}lcl} |
|
1146 \bl{$((\ONE \cdot b) + \ZERO) \cdot r$} |
|
1147 & \bl{$\Rightarrow$} & \bl{$((\underline{\ONE \cdot b}) + \ZERO) \cdot r$}\\ |
|
1148 & \bl{$=$} & \bl{$(\underline{b + \ZERO}) \cdot r$}\\ |
|
1149 & \bl{$=$} & \bl{$b \cdot r$}\\ |
|
1150 \end{tabular} |
|
1151 \end{center} |
|
1152 |
|
1153 \end{frame} |
|
1154 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1155 |
|
1156 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1157 \begin{frame}[c] |
|
1158 \frametitle{Proofs about Rexp} |
|
1159 |
|
1160 \begin{itemize} |
|
1161 \item \bl{$P$} holds for \bl{$\ZERO$}, \bl{$\ONE$} and \bl{c}\bigskip |
|
1162 \item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already |
|
1163 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip |
|
1164 \item \bl{$P$} holds for \bl{$r_1 \cdot r_2$} under the assumption that \bl{$P$} already |
|
1165 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip |
|
1166 \item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already |
|
1167 holds for \bl{$r$}. |
|
1168 \end{itemize} |
|
1169 |
|
1170 \end{frame} |
|
1171 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1172 |
|
1173 |
|
1174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1175 \begin{frame}[c] |
|
1176 |
|
1177 We proved |
|
1178 |
|
1179 \begin{center} |
|
1180 \bl{$nullable(r)$} \;if and only if\; \bl{$[] \in L(r)$} |
|
1181 \end{center} |
|
1182 |
|
1183 by induction on the regular expression \bl{$r$}.\bigskip\pause |
|
1184 |
|
1185 \begin{center} |
|
1186 {\huge\bf\alert{Any Questions?}} |
|
1187 \end{center} |
|
1188 |
|
1189 \end{frame} |
|
1190 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1191 |
|
1192 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1193 \begin{frame}[c] |
|
1194 \frametitle{\begin{tabular}{c}Proofs about Natural\\[-1mm] Numbers and Strings\end{tabular}} |
|
1195 |
|
1196 \begin{itemize} |
|
1197 \item \bl{$P$} holds for \bl{$0$} and |
|
1198 \item \bl{$P$} holds for \bl{$n + 1$} under the assumption that \bl{$P$} already |
|
1199 holds for \bl{$n$} |
|
1200 \end{itemize}\bigskip |
|
1201 |
|
1202 \begin{itemize} |
|
1203 \item \bl{$P$} holds for \bl{$[]$} and |
|
1204 \item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already |
|
1205 holds for \bl{$s$} |
|
1206 \end{itemize} |
|
1207 |
|
1208 \end{frame} |
|
1209 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1210 |
|
1211 |
|
1212 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1213 \begin{frame}[c] |
|
1214 \frametitle{Correctness Proof \\[-1mm] |
|
1215 for our Matcher} |
|
1216 |
|
1217 \begin{itemize} |
|
1218 \item We started from |
|
1219 |
|
1220 \begin{center} |
|
1221 \begin{tabular}{rp{4cm}} |
|
1222 & \bl{$s \in L(r)$}\medskip\\ |
|
1223 \bl{$\Leftrightarrow$} & \bl{$[] \in \Ders\,s\,(L(r))$}\pause |
|
1224 \end{tabular} |
|
1225 \end{center}\bigskip |
|
1226 |
|
1227 \item \textbf{\alert{if}} we can show \bl{$\Ders\, s\,(L(r)) = L(\ders\,s\,r)$} we |
|
1228 have\bigskip |
|
1229 |
|
1230 \begin{center} |
|
1231 \begin{tabular}{rp{4cm}} |
|
1232 \bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\ |
|
1233 \bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\ |
|
1234 \bl{$\dn$} & \bl{$matches\,s\,r$} |
|
1235 \end{tabular} |
|
1236 \end{center} |
|
1237 |
|
1238 \end{itemize} |
|
1239 |
|
1240 \end{frame} |
|
1241 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1242 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1243 \begin{frame}[c] |
|
1244 |
|
1245 We need to prove |
|
1246 |
|
1247 \begin{center} |
|
1248 \bl{$L(der\,c\,r) = Der\,c\,(L(r))$} |
|
1249 \end{center} |
|
1250 |
|
1251 also by induction on the regular expression \bl{$r$}. |
|
1252 \end{frame} |
|
1253 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1254 |
|
1255 |
|
1256 |
1224 |
1257 |
1225 \end{document} |
1258 \end{document} |
1226 |
1259 |
1227 %%% Local Variables: |
1260 %%% Local Variables: |
1228 %%% mode: latex |
1261 %%% mode: latex |