103 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
103 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
104 \mode<presentation>{ |
104 \mode<presentation>{ |
105 \begin{frame}[c] |
105 \begin{frame}[c] |
106 \frametitle{\begin{tabular}{c}Last Week\end{tabular}} |
106 \frametitle{\begin{tabular}{c}Last Week\end{tabular}} |
107 |
107 |
108 Last week I showed you |
108 Last week I showed you\bigskip |
109 |
109 |
110 \begin{itemize} |
110 \begin{itemize} |
111 \item tokenizer |
111 \item a tokenizer taking a list of regular expressions\bigskip |
112 |
112 |
113 \item tokenization identifies lexeme in an input stream of characters (or string) |
113 \item tokenization identifies lexeme in an input stream of characters (or string) |
114 and categorizes them into tokens |
114 and cathegorizes them into tokens |
115 |
115 |
116 \item longest match rule (maximal munch rule): The |
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 |
117 longest initial substring matched by any regular expression is taken |
128 longest initial substring matched by any regular expression is taken |
118 as next token. |
129 as next token.\bigskip |
119 |
130 |
120 \item Rule priority: |
131 \item Rule priority: |
121 For a particular longest initial substring, the first regular |
132 For a particular longest initial substring, the first regular |
122 expression that can match determines the token. |
133 expression that can match determines the token. |
123 |
134 |
124 \item problem with infix operations, for example i-12 |
135 \end{itemize} |
125 \end{itemize} |
136 |
126 |
137 %\url{http://www.technologyreview.com/tr10/?year=2011} |
127 \url{http://www.technologyreview.com/tr10/?year=2011} |
|
128 |
138 |
129 finite deterministic automata/ nondeterministic automaton |
139 %finite deterministic automata/ nondeterministic automaton |
130 |
140 |
131 |
141 %\item problem with infix operations, for example i-12 |
132 |
142 |
133 \end{frame}} |
|
134 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
135 |
|
136 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
137 \mode<presentation>{ |
|
138 \begin{frame}[c] |
|
139 \frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}} |
|
140 |
|
141 \begin{center} |
|
142 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
|
143 \bl{der c ($\varnothing$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
|
144 \bl{der c ($\epsilon$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
|
145 \bl{der c (d)} & \bl{$\dn$} & \bl{if c $=$ d then $\epsilon$ else $\varnothing$} & \\ |
|
146 \bl{der c (r$_1$ + r$_2$)} & \bl{$\dn$} & \bl{(der c r$_1$) + (der c r$_2$)} & \\ |
|
147 \bl{der c (r$_1$ $\cdot$ r$_2$)} & \bl{$\dn$} & \bl{if nullable r$_1$}\\ |
|
148 & & \bl{then ((der c r$_1$) $\cdot$ r$_2$) + (der c r$_2$)}\\ |
|
149 & & \bl{else (der c r$_1$) $\cdot$ r$_2$}\\ |
|
150 \bl{der c (r$^*$)} & \bl{$\dn$} & \bl{(der c r) $\cdot$ (r$^*$)}\\ |
|
151 \end{tabular} |
|
152 \end{center} |
|
153 |
|
154 ``the regular expression after \bl{c} has been recognised'' |
|
155 |
|
156 \end{frame}} |
|
157 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
158 |
|
159 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
160 \mode<presentation>{ |
|
161 \begin{frame}[c] |
|
162 |
|
163 For this we defined the set \bl{Der c A} as |
|
164 |
|
165 \begin{center} |
|
166 \bl{Der c A $\dn$ $\{$ s $|$ c::s $\in$ A$\}$ } |
|
167 \end{center} |
|
168 |
|
169 which is called the semantic derivative of a set |
|
170 and proved |
|
171 |
|
172 \begin{center} |
|
173 \bl{$L$(der c r) $=$ Der c ($L$(r))} |
|
174 \end{center} |
|
175 |
|
176 |
|
177 \end{frame}} |
|
178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
179 |
|
180 |
|
181 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
182 \mode<presentation>{ |
|
183 \begin{frame}[c] |
|
184 \frametitle{\begin{tabular}{c}The Idea of the Algorithm\end{tabular}} |
|
185 |
|
186 If we want to recognise the string \bl{abc} with regular expression \bl{r} |
|
187 then\medskip |
|
188 |
|
189 \begin{enumerate} |
|
190 \item \bl{Der a ($L$(r))}\pause |
|
191 \item \bl{Der b (Der a ($L$(r)))} |
|
192 \item \bl{Der c (Der b (Der a ($L$(r))))}\pause |
|
193 \item finally we test whether the empty string is in set\pause\medskip |
|
194 \end{enumerate} |
|
195 |
|
196 The matching algorithm works similarly, just over regular expression than sets. |
|
197 \end{frame}} |
|
198 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
199 |
|
200 |
|
201 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
202 \mode<presentation>{ |
|
203 \begin{frame}[c] |
|
204 |
|
205 Input: string \bl{abc} and regular expression \bl{r} |
|
206 |
|
207 \begin{enumerate} |
|
208 \item \bl{der a r} |
|
209 \item \bl{der b (der a r)} |
|
210 \item \bl{der c (der b (der a r))}\pause |
|
211 \item finally check whether the latter regular expression can match the empty string |
|
212 \end{enumerate} |
|
213 |
|
214 \end{frame}} |
|
215 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
216 |
|
217 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
218 \mode<presentation>{ |
|
219 \begin{frame}[c] |
|
220 |
|
221 We need to prove |
|
222 |
|
223 \begin{center} |
|
224 \bl{$L$(der c r) $=$ Der c ($L$(r))} |
|
225 \end{center} |
|
226 |
|
227 by induction on the regular expression. |
|
228 |
|
229 \end{frame}} |
|
230 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
231 |
|
232 |
|
233 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
234 \mode<presentation>{ |
|
235 \begin{frame}[c] |
|
236 \frametitle{\begin{tabular}{c}Proofs about Rexp\end{tabular}} |
|
237 |
|
238 \begin{itemize} |
|
239 \item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip |
|
240 \item \bl{$P$} holds for \bl{r$_1$ + r$_2$} under the assumption that \bl{$P$} already |
|
241 holds for \bl{r$_1$} and \bl{r$_2$}.\bigskip |
|
242 \item \bl{$P$} holds for \bl{r$_1$ $\cdot$ r$_2$} under the assumption that \bl{$P$} already |
|
243 holds for \bl{r$_1$} and \bl{r$_2$}. |
|
244 \item \bl{$P$} holds for \bl{r$^*$} under the assumption that \bl{$P$} already |
|
245 holds for \bl{r}. |
|
246 \end{itemize} |
|
247 |
|
248 \end{frame}} |
|
249 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
250 |
|
251 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
252 \mode<presentation>{ |
|
253 \begin{frame}[c] |
|
254 \frametitle{\begin{tabular}{c}Proofs about Natural Numbers\\ and Strings\end{tabular}} |
|
255 |
|
256 \begin{itemize} |
|
257 \item \bl{$P$} holds for \bl{$0$} and |
|
258 \item \bl{$P$} holds for \bl{$n + 1$} under the assumption that \bl{$P$} already |
|
259 holds for \bl{$n$} |
|
260 \end{itemize}\bigskip |
|
261 |
|
262 \begin{itemize} |
|
263 \item \bl{$P$} holds for \bl{\texttt{""}} and |
|
264 \item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already |
|
265 holds for \bl{$s$} |
|
266 \end{itemize} |
|
267 |
143 |
268 \end{frame}} |
144 \end{frame}} |
269 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
145 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
270 |
146 |
271 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
147 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
272 \mode<presentation>{ |
148 \mode<presentation>{ |
273 \begin{frame}[t] |
149 \begin{frame}[t] |
274 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
150 |
275 |
151 \begin{center} |
276 \begin{center} |
152 \texttt{"if true then then 42 else +"} |
277 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
153 \end{center} |
278 \bl{r} & \bl{$::=$} & \bl{$\varnothing$} & null\\ |
154 |
279 & \bl{$\mid$} & \bl{$\epsilon$} & empty string / "" / []\\ |
155 \only<1>{ |
280 & \bl{$\mid$} & \bl{c} & character\\ |
156 \small\begin{tabular}{l} |
281 & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$} & sequence\\ |
157 KEYWORD(if),\\ |
282 & \bl{$\mid$} & \bl{r$_1$ + r$_2$} & alternative / choice\\ |
158 WHITESPACE,\\ |
283 & \bl{$\mid$} & \bl{r$^*$} & star (zero or more)\\ |
159 IDENT(true),\\ |
284 \end{tabular}\bigskip\pause |
160 WHITESPACE,\\ |
285 \end{center} |
161 KEYWORD(then),\\ |
286 |
162 WHITESPACE,\\ |
287 \end{frame}} |
163 KEYWORD(then),\\ |
288 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
164 WHITESPACE,\\ |
289 |
165 NUM(42),\\ |
290 |
166 WHITESPACE,\\ |
291 |
167 KEYWORD(else),\\ |
292 |
168 WHITESPACE,\\ |
293 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
169 OP(+) |
294 \mode<presentation>{ |
170 \end{tabular}} |
295 \begin{frame}[c] |
171 |
296 \frametitle{\begin{tabular}{c}Languages\end{tabular}} |
172 \only<2>{ |
297 |
173 \small\begin{tabular}{l} |
298 A \alert{language} is a set of strings.\bigskip |
174 KEYWORD(if),\\ |
299 |
175 IDENT(true),\\ |
300 A \alert{regular expression} specifies a set of strings or language.\bigskip |
176 KEYWORD(then),\\ |
301 |
177 KEYWORD(then),\\ |
302 A language is \alert{regular} iff there exists |
178 NUM(42),\\ |
303 a regular expression that recognises all its strings.\bigskip\bigskip\pause |
179 KEYWORD(else),\\ |
304 |
180 OP(+) |
305 \textcolor{gray}{not all languages are regular, e.g.~\bl{a$^n$b$^n$}.} |
181 \end{tabular}} |
306 \end{frame}} |
182 |
307 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
183 \end{frame}} |
308 |
184 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
309 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
185 |
310 \mode<presentation>{ |
186 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
311 \begin{frame}[t] |
187 \mode<presentation>{ |
312 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
188 \begin{frame}[c] |
313 |
189 |
314 \begin{center} |
190 |
315 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
191 There is one small problem with the tokenizer. How should we |
316 \bl{r} & \bl{$::=$} & \bl{$\varnothing$} & null\\ |
192 tokenize: |
317 & \bl{$\mid$} & \bl{$\epsilon$} & empty string / "" / []\\ |
193 |
318 & \bl{$\mid$} & \bl{c} & character\\ |
194 \begin{center} |
319 & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$} & sequence\\ |
195 \texttt{"x - 3"} |
320 & \bl{$\mid$} & \bl{r$_1$ + r$_2$} & alternative / choice\\ |
196 \end{center} |
321 & \bl{$\mid$} & \bl{r$^*$} & star (zero or more)\\ |
197 |
322 \end{tabular}\bigskip |
198 \end{frame}} |
323 \end{center} |
199 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
324 |
200 |
325 How about ranges \bl{[a-z]}, \bl{r$^\text{+}$} and \bl{!r}? |
201 |
326 |
202 |
327 \end{frame}} |
|
328 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
329 |
|
330 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
331 \mode<presentation>{ |
|
332 \begin{frame}[c] |
|
333 \frametitle{\begin{tabular}{c}Negation of Regular Expr's\end{tabular}} |
|
334 |
|
335 \begin{itemize} |
|
336 \item \bl{!r} \hspace{6mm} (everything that \bl{r} cannot recognise)\medskip |
|
337 \item \bl{$L$(!r) $\dn$ UNIV - $L$(r)}\medskip |
|
338 \item \bl{nullable (!r) $\dn$ not (nullable(r))}\medskip |
|
339 \item \bl{der\,c\,(!r) $\dn$ !(der\,c\,r)} |
|
340 \end{itemize} |
|
341 |
|
342 \end{frame}} |
|
343 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
344 |
|
345 |
|
346 |
|
347 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
348 \mode<presentation>{ |
|
349 \begin{frame}[c] |
|
350 \frametitle{\begin{tabular}{c}Regular Exp's for Lexing\end{tabular}} |
|
351 |
|
352 Lexing separates strings into ``words'' / components. |
|
353 |
|
354 \begin{itemize} |
|
355 \item Identifiers (non-empty strings of letters or digits, starting with a letter) |
|
356 \item Numbers (non-empty sequences of digits omitting leading zeros) |
|
357 \item Keywords (else, if, while, \ldots) |
|
358 \item White space (a non-empty sequence of blanks, newlines and tabs) |
|
359 \item Comments |
|
360 \end{itemize} |
|
361 |
|
362 \end{frame}} |
|
363 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
364 |
203 |
365 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
204 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
366 \mode<presentation>{ |
205 \mode<presentation>{ |
367 \begin{frame}[c] |
206 \begin{frame}[c] |
368 \frametitle{\begin{tabular}{c}Automata\end{tabular}} |
207 \frametitle{\begin{tabular}{c}Automata\end{tabular}} |
369 |
208 |
370 A deterministic finite automaton consists of: |
209 A deterministic finite automaton consists of: |
371 |
210 |
372 \begin{itemize} |
211 \begin{itemize} |
373 \item a set of states |
212 \item a finite set of states |
374 \item one of these states is the start state |
213 \item one of these states is the start state |
375 \item some states are accepting states, and |
214 \item some states are accepting states, and |
376 \item there is transition function\medskip |
215 \item there is transition function\medskip |
377 |
216 |
378 \small |
217 \small |
379 which takes a state as argument and a character and produces a new state\smallskip\\ |
218 which takes a state and a character as arguments and produces a new state\smallskip\\ |
380 this function might not always be defined |
219 this function might not always be defined everywhere |
|
220 \end{itemize} |
|
221 |
|
222 \begin{center} |
|
223 \bl{$A(Q, q_0, F, \delta)$} |
|
224 \end{center} |
|
225 \end{frame}} |
|
226 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
227 |
|
228 |
|
229 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
230 \mode<presentation>{ |
|
231 \begin{frame}[c] |
|
232 |
|
233 \begin{center} |
|
234 \includegraphics[scale=0.7]{pics/ch3.jpg} |
|
235 \end{center} |
|
236 |
|
237 \end{frame}} |
|
238 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
239 |
|
240 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
241 \mode<presentation>{ |
|
242 \begin{frame}[t] |
|
243 \frametitle{\begin{tabular}{c}Accepting a String\end{tabular}} |
|
244 |
|
245 \begin{center} |
|
246 \bl{$A(Q, q_0, F, \delta)$} |
|
247 \end{center}\bigskip |
|
248 |
|
249 \begin{center} |
|
250 \begin{tabular}{l} |
|
251 \bl{$\hat{\delta}(\texttt{""}, q) = q$}\\ |
|
252 \bl{$\hat{\delta}(c::s, q) = \hat{\delta}(s, \delta(c, q))$}\\ |
|
253 \end{tabular} |
|
254 \end{center}\bigskip\pause |
|
255 |
|
256 \begin{center} |
|
257 Accepting? \hspace{5mm}\bl{$\hat{\delta}(s, q_0) \in F$} |
|
258 \end{center} |
|
259 \end{frame}} |
|
260 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
261 |
|
262 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
263 \mode<presentation>{ |
|
264 \begin{frame}[c] |
|
265 |
|
266 \begin{center} |
|
267 \includegraphics[scale=0.7]{pics/ch4.jpg} |
|
268 \end{center} |
|
269 |
|
270 \end{frame}} |
|
271 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
272 |
|
273 |
|
274 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
275 \mode<presentation>{ |
|
276 \begin{frame}[c] |
|
277 \frametitle{\begin{tabular}{c}Languages\end{tabular}} |
|
278 |
|
279 A language is \alert{regular} iff there exists |
|
280 a regular expression that recognises all its strings.\bigskip\bigskip\pause |
|
281 |
|
282 \textcolor{gray}{not all languages are regular, e.g.~\bl{a$^n$b$^n$}.} |
|
283 \end{frame}} |
|
284 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
285 |
|
286 |
|
287 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
288 \mode<presentation>{ |
|
289 \begin{frame}[c] |
|
290 |
|
291 |
|
292 |
|
293 \begin{itemize} |
|
294 \item Assuming you have the alphabet \bl{\{a, b, c\}}\bigskip |
|
295 \item Give a regular expression that can recognise all strings that have at least one \bl{b}. |
|
296 \end{itemize} |
|
297 |
|
298 \end{frame}} |
|
299 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
300 |
|
301 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
302 \mode<presentation>{ |
|
303 \begin{frame}[c] |
|
304 |
|
305 |
|
306 |
|
307 \begin{itemize} |
|
308 \item The star-case in our proof needs the following lemma |
|
309 \begin{center} |
|
310 \bl{Der\,c\,A$^*$ $=$ (Der c A)\,@\, A$^*$} |
|
311 \end{center} |
|
312 \end{itemize}\bigskip\bigskip |
|
313 |
|
314 |
|
315 |
|
316 \begin{itemize} |
|
317 \item If \bl{\texttt{""} $\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B $\cup$ (Der\,c\,B)}\medskip |
|
318 \item If \bl{\texttt{""} $\not\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B} |
|
319 |
381 \end{itemize} |
320 \end{itemize} |
382 |
321 |
383 \end{frame}} |
322 \end{frame}} |
384 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
323 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
385 |
324 |