equal
deleted
inserted
replaced
176 When Are Two Regular\\[-1mm] |
176 When Are Two Regular\\[-1mm] |
177 Expressions Equivalent?} |
177 Expressions Equivalent?} |
178 |
178 |
179 \begin{bubble}[10cm] |
179 \begin{bubble}[10cm] |
180 \large |
180 \large |
181 Two regular expressions \bl{$r_1$} and \bl{$r_2$} are equivalent |
181 Two regular expressions \bl{$r_1$} and \bl{$r_2$} are |
|
182 \alert{\bf{}equivalent} |
182 provided:\medskip |
183 provided:\medskip |
183 \begin{center} |
184 \begin{center} |
184 \bl{$r_1 \equiv r_2 \;\;\dn\;\; L(r_1) = L(r_2)$} |
185 \bl{$r_1 \equiv r_2 \;\;\dn\;\; L(r_1) = L(r_2)$} |
185 \end{center}\medskip |
186 \end{center}\medskip |
186 \end{bubble} |
187 \end{bubble} |
241 \end{center} |
242 \end{center} |
242 |
243 |
243 \end{frame} |
244 \end{frame} |
244 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
245 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
245 |
246 |
246 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
247 \begin{frame}[c] |
|
248 \frametitle{The Specification for Matching} |
|
249 |
|
250 \begin{bubble}[10cm] |
|
251 \large |
|
252 A regular expression \bl{$r$} matches a string~\bl{$s$} |
|
253 provided: |
|
254 \begin{center} |
|
255 \bl{$s \in L(r)$} |
|
256 \end{center}\medskip |
|
257 \end{bubble} |
|
258 |
|
259 \bigskip\bigskip |
|
260 |
|
261 \ldots and the point of the this lecture is to decide this problem as |
|
262 fast as possible (unlike Python, Ruby, Java etc) |
|
263 |
|
264 \end{frame} |
|
265 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
266 |
|
267 |
|
268 |
|
269 |
247 |
270 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
248 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
271 \begin{frame}[t] |
249 \begin{frame}[t] |
272 \frametitle{Semantic Derivative\\[5mm]} |
250 \frametitle{Semantic Derivative\\[5mm]} |
273 |
251 |
299 \end{itemize} |
277 \end{itemize} |
300 |
278 |
301 \end{frame} |
279 \end{frame} |
302 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
280 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
303 |
281 |
|
282 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
283 \begin{frame}[c] |
|
284 \frametitle{The Specification for Matching} |
|
285 |
|
286 \begin{bubble}[10cm] |
|
287 \large |
|
288 A regular expression \bl{$r$} matches a string~\bl{$s$} |
|
289 provided: |
|
290 \begin{center} |
|
291 \bl{$s \in L(r)$} |
|
292 \end{center}\medskip |
|
293 \end{bubble} |
|
294 |
|
295 \bigskip\bigskip |
|
296 |
|
297 \ldots and the point of the this lecture is to decide this problem as |
|
298 fast as possible (unlike Python, Ruby, Java etc) |
|
299 |
|
300 \end{frame} |
|
301 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
302 |
304 |
303 |
305 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
304 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
306 \begin{frame}[c] |
305 \begin{frame}[c] |
307 \frametitle{\mbox{Brzozowski's Algorithm (1)}} |
306 \frametitle{\mbox{Brzozowski's Algorithm (1)}} |
308 |
307 |