equal
deleted
inserted
replaced
163 \end{frame} |
163 \end{frame} |
164 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
164 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
165 |
165 |
166 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
166 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
167 \begin{frame}[c] |
167 \begin{frame}[c] |
|
168 \frametitle{Homework Question} |
|
169 |
|
170 \begin{itemize} |
|
171 \item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip |
|
172 |
|
173 \begin{center} |
|
174 How many strings are in \bl{$A^4$}? |
|
175 \end{center}\bigskip\medskip\pause |
|
176 |
|
177 |
|
178 \begin{center} |
|
179 \begin{tabular}{l} |
|
180 What if \bl{$A = \{[a],[b],[c],[]\}$};\\ |
|
181 how many strings are then in \bl{$A^4$}? |
|
182 \end{tabular} |
|
183 \end{center} |
|
184 \end{itemize} |
|
185 |
|
186 \end{frame} |
|
187 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
188 |
|
189 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
190 \begin{frame}[c] |
168 \frametitle{The Star Operation} |
191 \frametitle{The Star Operation} |
169 |
192 |
170 \begin{itemize} |
193 \begin{itemize} |
171 \item The \alert{\bf Star} of a \underline{language}: |
194 \item The \alert{\bf Star} of a \underline{language}: |
172 \bigskip |
195 \bigskip |
236 & \bl{$\mid$} & \bl{$c$} & character\\ |
259 & \bl{$\mid$} & \bl{$c$} & character\\ |
237 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\ |
260 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\ |
238 & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\ |
261 & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\ |
239 & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\ |
262 & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\ |
240 \end{tabular} |
263 \end{tabular} |
241 \end{textblock} |
264 \end{textblock} |
242 |
265 |
243 |
|
244 \end{frame} |
266 \end{frame} |
245 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
267 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
246 |
268 |
247 |
269 |
248 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
270 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
259 \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))^*$}\\ |
281 \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))^*$}\\ |
260 \end{tabular} |
282 \end{tabular} |
261 \end{textblock} |
283 \end{textblock} |
262 |
284 |
263 \begin{textblock}{6}(9,12)\small |
285 \begin{textblock}{6}(9,12)\small |
264 \bl{$L$} is a function from regular expressions to sets of strings\\ |
286 \bl{$L$} is a function from regular expressions to |
|
287 sets of strings\\ |
265 \bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
288 \bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
266 \end{textblock} |
289 \end{textblock} |
267 |
290 |
268 \end{frame} |
291 \end{frame} |
269 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
292 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
292 \end{frame} |
315 \end{frame} |
293 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
316 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
294 |
317 |
295 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
318 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
296 \begin{frame}[t] |
319 \begin{frame}[t] |
297 \frametitle{\begin{tabular}{c}Concrete Equivalences\end{tabular}} |
320 \frametitle{Concrete Equivalences} |
298 |
321 |
299 \begin{center} |
322 \begin{center} |
300 \bl{\begin{tabular}{rcl} |
323 \bl{\begin{tabular}{rcl} |
301 $(a + b) + c$ & $\equiv$ & $a + (b + c)$\\ |
324 $(a + b) + c$ & $\equiv$ & $a + (b + c)$\\ |
302 $a + a$ & $\equiv$ & $a$\\ |
325 $a + a$ & $\equiv$ & $a$\\ |
311 \end{frame} |
334 \end{frame} |
312 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
335 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
313 |
336 |
314 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
337 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
315 \begin{frame}[t] |
338 \begin{frame}[t] |
316 \frametitle{\begin{tabular}{c}Corner Cases\end{tabular}} |
339 \frametitle{Corner Cases} |
317 |
340 |
318 \begin{center} |
341 \begin{center} |
319 \bl{\begin{tabular}{rcl} |
342 \bl{\begin{tabular}{rcl} |
320 $a \cdot \varnothing$ & $\not\equiv$ & $a$\\ |
343 $a \cdot \varnothing$ & $\not\equiv$ & $a$\\ |
321 $a + \epsilon$ & $\not\equiv$ & $a$\\ |
344 $a + \epsilon$ & $\not\equiv$ & $a$\\ |
328 \end{frame} |
351 \end{frame} |
329 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
352 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
330 |
353 |
331 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
354 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
332 \begin{frame}[t] |
355 \begin{frame}[t] |
333 \frametitle{\begin{tabular}{c}Simplification Rules\end{tabular}} |
356 \frametitle{Simplification Rules} |
334 |
357 |
335 \begin{center} |
358 \begin{center} |
336 \bl{\begin{tabular}{rcl} |
359 \bl{\begin{tabular}{rcl} |
337 $r + \varnothing$ & $\equiv$ & $r$\\ |
360 $r + \varnothing$ & $\equiv$ & $r$\\ |
338 $\varnothing + r$ & $\equiv$ & $r$\\ |
361 $\varnothing + r$ & $\equiv$ & $r$\\ |