22 |
22 |
23 \definecolor{javared}{rgb}{0.6,0,0} % for strings |
23 \definecolor{javared}{rgb}{0.6,0,0} % for strings |
24 \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments |
24 \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments |
25 \definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords |
25 \definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords |
26 \definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc |
26 \definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc |
|
27 \makeatletter |
|
28 \lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}} |
|
29 \@empty\z@\@empty |
|
30 \makeatother |
27 |
31 |
28 \lstset{language=Java, |
32 \lstset{language=Java, |
29 basicstyle=\ttfamily, |
33 basicstyle=\consolas, |
30 keywordstyle=\color{javapurple}\bfseries, |
34 keywordstyle=\color{javapurple}\bfseries, |
31 stringstyle=\color{javagreen}, |
35 stringstyle=\color{javagreen}, |
32 commentstyle=\color{javagreen}, |
36 commentstyle=\color{javagreen}, |
33 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
37 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
34 numbers=left, |
38 numbers=left, |
45 for,if,implicit,import,match,mixin,% |
49 for,if,implicit,import,match,mixin,% |
46 new,null,object,override,package,% |
50 new,null,object,override,package,% |
47 private,protected,requires,return,sealed,% |
51 private,protected,requires,return,sealed,% |
48 super,this,throw,trait,true,try,% |
52 super,this,throw,trait,true,try,% |
49 type,val,var,while,with,yield}, |
53 type,val,var,while,with,yield}, |
50 otherkeywords={=>,<-,<\%,<:,>:,\#,@}, |
54 otherkeywords={=>,<-,<\%,<:,>:,\#,@,->}, |
51 sensitive=true, |
55 sensitive=true, |
52 morecomment=[l]{//}, |
56 morecomment=[l]{//}, |
53 morecomment=[n]{/*}{*/}, |
57 morecomment=[n]{/*}{*/}, |
54 morestring=[b]", |
58 morestring=[b]", |
55 morestring=[b]', |
59 morestring=[b]', |
56 morestring=[b]""" |
60 morestring=[b]""" |
57 } |
61 } |
58 |
62 |
59 \lstset{language=Scala, |
63 \lstset{language=Scala, |
60 basicstyle=\ttfamily, |
64 basicstyle=\consolas, |
61 keywordstyle=\color{javapurple}\bfseries, |
65 keywordstyle=\color{javapurple}\bfseries, |
62 stringstyle=\color{javagreen}, |
66 stringstyle=\color{javagreen}, |
63 commentstyle=\color{javagreen}, |
67 commentstyle=\color{javagreen}, |
64 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
68 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
65 numbers=left, |
69 numbers=left, |
95 |
100 |
96 \normalsize |
101 \normalsize |
97 \begin{center} |
102 \begin{center} |
98 \begin{tabular}{ll} |
103 \begin{tabular}{ll} |
99 Email: & christian.urban at kcl.ac.uk\\ |
104 Email: & christian.urban at kcl.ac.uk\\ |
100 Of$\!$fice: & S1.27 (1st floor Strand Building)\\ |
105 Office: & S1.27 (1st floor Strand Building)\\ |
101 Slides: & KEATS (also home work is there)\\ |
106 Slides: & KEATS (also home work is there)\\ |
102 & \alert{\bf (I have put a temporary link in there.)}\\ |
|
103 \end{tabular} |
107 \end{tabular} |
104 \end{center} |
108 \end{center} |
105 |
109 |
106 |
110 |
107 \end{frame}} |
111 \end{frame}} |
108 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
112 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
109 |
113 |
110 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
114 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
111 \mode<presentation>{ |
115 \mode<presentation>{ |
112 \begin{frame}[c] |
116 \begin{frame}[c] |
|
117 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
|
118 |
|
119 They are often used to recognise:\medskip |
|
120 |
|
121 \begin{itemize} |
|
122 \item symbols, digits |
|
123 \item identifiers |
|
124 \item numbers (non-leading zeros) |
|
125 \item keywords |
|
126 \item comments |
|
127 \end{itemize}\bigskip |
|
128 |
|
129 |
|
130 \mbox{}\hfill\bl{\url{http://www.regexper.com}} |
|
131 \end{frame}} |
|
132 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
133 |
|
134 |
|
135 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
136 \mode<presentation>{ |
|
137 \begin{frame}[c] |
113 \frametitle{\begin{tabular}{c}Last Week\end{tabular}} |
138 \frametitle{\begin{tabular}{c}Last Week\end{tabular}} |
114 |
139 |
115 Last week I showed you |
140 Last week I showed you a regular expression matcher |
116 |
141 which works provably in all cases. |
117 \begin{itemize} |
142 |
118 \item one simple-minded regular expression matcher (which however does not work in all cases), and\bigskip |
143 \begin{center} |
119 \item one which works provably in all cases |
144 \bl{$matcher\,r\,s$} \;\;if and only if \;\; \bl{$s \in L(r)$} |
120 |
145 \end{center}\bigskip\bigskip |
121 \begin{center} |
146 |
122 \bl{matcher r s} \;\;if and only if \;\; \bl{s $\in$ $L$(r)} |
147 \small |
123 \end{center} |
148 \textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)} |
124 \end{itemize} |
149 |
125 |
150 |
126 \end{frame}} |
151 \end{frame}} |
127 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
152 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
128 |
153 |
129 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
154 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
131 \begin{frame}[c] |
156 \begin{frame}[c] |
132 \frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}} |
157 \frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}} |
133 |
158 |
134 \begin{center} |
159 \begin{center} |
135 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
160 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
136 \bl{der c ($\varnothing$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
161 \bl{$der\, c\, (\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
137 \bl{der c ($\epsilon$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
162 \bl{$der\, c\, (\epsilon)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
138 \bl{der c (d)} & \bl{$\dn$} & \bl{if c $=$ d then $\epsilon$ else $\varnothing$} & \\ |
163 \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\ |
139 \bl{der c (r$_1$ + r$_2$)} & \bl{$\dn$} & \bl{(der c r$_1$) + (der c r$_2$)} & \\ |
164 \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\ |
140 \bl{der c (r$_1$ $\cdot$ r$_2$)} & \bl{$\dn$} & \bl{if nullable r$_1$}\\ |
165 \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ |
141 & & \bl{then ((der c r$_1$) $\cdot$ r$_2$) + (der c r$_2$)}\\ |
166 & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ |
142 & & \bl{else (der c r$_1$) $\cdot$ r$_2$}\\ |
167 & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\ |
143 \bl{der c (r$^*$)} & \bl{$\dn$} & \bl{(der c r) $\cdot$ (r$^*$)}\\ |
168 \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\smallskip\\\pause |
|
169 |
|
170 \bl{$der\!s\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ |
|
171 \bl{$der\!s\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\ |
144 \end{tabular} |
172 \end{tabular} |
145 \end{center} |
173 \end{center} |
146 |
174 |
147 ``the regular expression after \bl{c} has been recognised'' |
175 |
148 |
176 \end{frame}} |
149 \end{frame}} |
177 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
150 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
178 |
151 |
179 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
152 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
180 \mode<presentation>{ |
153 \mode<presentation>{ |
181 \begin{frame}[c] |
154 \begin{frame}[c] |
182 |
155 |
183 |
156 For this we defined the set \bl{Der c A} as |
184 To see what is going on, define |
157 |
185 |
158 \begin{center} |
186 \begin{center} |
159 \bl{Der c A $\dn$ $\{$ s $|$ c::s $\in$ A$\}$ } |
187 \bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } |
|
188 \end{center}\bigskip\bigskip |
|
189 |
|
190 \small |
|
191 For \bl{$A = \{"f\!oo", "bar", "f\!rak"\}$} then |
|
192 |
|
193 \begin{center} |
|
194 \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} |
|
195 $Der\,f\,A$ & $=$ & $\{"oo", "rak"\}$\\ |
|
196 $Der\,b\,A$ & $=$ & $\{"ar"\}$\\ |
|
197 $Der\,a\,A$ & $=$ & $\varnothing$\\ |
|
198 \end{tabular}} |
160 \end{center} |
199 \end{center} |
161 |
200 |
162 which is called the semantic derivative of a set |
|
163 and proved |
|
164 |
|
165 \begin{center} |
|
166 \bl{$L$(der c r) $=$ Der c ($L$(r))} |
|
167 \end{center} |
|
168 |
|
169 |
201 |
170 \end{frame}} |
202 \end{frame}} |
171 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
203 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
172 |
204 |
173 |
205 |
174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
206 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
175 \mode<presentation>{ |
207 \mode<presentation>{ |
176 \begin{frame}[c] |
208 \begin{frame}[c] |
177 \frametitle{\begin{tabular}{c}The Idea of the Algorithm\end{tabular}} |
209 \frametitle{\begin{tabular}{c}The Idea of the Algorithm\end{tabular}} |
178 |
210 |
179 If we want to recognise the string \bl{abc} with regular expression \bl{r} |
211 If we want to recognise the string \bl{$"abc"$} with regular expression \bl{$r$} |
180 then\medskip |
212 then\medskip |
181 |
213 |
182 \begin{enumerate} |
214 \begin{enumerate} |
183 \item \bl{Der a ($L$(r))}\pause |
215 \item \bl{$Der\,a\,(L(r))$}\pause |
184 \item \bl{Der b (Der a ($L$(r)))} |
216 \item \bl{$Der\,b\,(Der\,a\,(L(r)))$}\pause |
185 \item \bl{Der c (Der b (Der a ($L$(r))))}\pause |
217 \item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r))))$}\pause |
186 \item finally we test whether the empty string is in set\pause\medskip |
218 \item finally we test whether the empty string is in this set\pause\medskip |
187 \end{enumerate} |
219 \end{enumerate} |
188 |
220 |
189 The matching algorithm works similarly, just over regular expression than sets. |
221 The matching algorithm works similarly, just over regular expression than sets. |
190 \end{frame}} |
222 \end{frame}} |
191 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
223 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
193 |
225 |
194 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
226 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
195 \mode<presentation>{ |
227 \mode<presentation>{ |
196 \begin{frame}[c] |
228 \begin{frame}[c] |
197 |
229 |
198 Input: string \bl{abc} and regular expression \bl{r} |
230 Input: string \bl{$"abc"$} and regular expression \bl{$r$} |
199 |
231 |
200 \begin{enumerate} |
232 \begin{enumerate} |
201 \item \bl{der a r} |
233 \item \bl{$der\,a\,r$} |
202 \item \bl{der b (der a r)} |
234 \item \bl{$der\,b\,(der\,a\,r)$} |
203 \item \bl{der c (der b (der a r))}\pause |
235 \item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause |
204 \item finally check whether the latter regular expression can match the empty string |
236 \item finally check whether the latter regular expression can match the empty string |
205 \end{enumerate} |
237 \end{enumerate} |
206 |
238 |
207 \end{frame}} |
239 \end{frame}} |
208 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
240 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
209 |
241 |
210 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
242 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
211 \mode<presentation>{ |
243 \mode<presentation>{ |
212 \begin{frame}[c] |
244 \begin{frame}[c] |
213 |
245 |
|
246 We proved already |
|
247 |
|
248 \begin{center} |
|
249 \bl{$nullable(r)$} \;if and only if\; \bl{$"" \in L(r)$} |
|
250 \end{center} |
|
251 |
|
252 by induction on the regular expression. |
|
253 |
|
254 \end{frame}} |
|
255 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
256 |
|
257 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
258 \mode<presentation>{ |
|
259 \begin{frame}[c] |
|
260 |
214 We need to prove |
261 We need to prove |
215 |
262 |
216 \begin{center} |
263 \begin{center} |
217 \bl{$L$(der c r) $=$ Der c ($L$(r))} |
264 \bl{$L(der\,c\,r) = Der\,c\,(L(r))$} |
218 \end{center} |
265 \end{center} |
219 |
266 |
220 by induction on the regular expression. |
267 by induction on the regular expression. |
221 |
268 |
222 \end{frame}} |
269 \end{frame}} |
224 |
271 |
225 |
272 |
226 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
273 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
227 \mode<presentation>{ |
274 \mode<presentation>{ |
228 \begin{frame}[c] |
275 \begin{frame}[c] |
229 \frametitle{\begin{tabular}{c}Proofs about Rexp\end{tabular}} |
276 \frametitle{\begin{tabular}{c}Proofs about Rexps\end{tabular}} |
230 |
277 |
231 \begin{itemize} |
278 \begin{itemize} |
232 \item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip |
279 \item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip |
233 \item \bl{$P$} holds for \bl{r$_1$ + r$_2$} under the assumption that \bl{$P$} already |
280 \item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already |
234 holds for \bl{r$_1$} and \bl{r$_2$}.\bigskip |
281 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip |
235 \item \bl{$P$} holds for \bl{r$_1$ $\cdot$ r$_2$} under the assumption that \bl{$P$} already |
282 \item \bl{$P$} holds for \bl{$r_1 \cdot r_2$} under the assumption that \bl{$P$} already |
236 holds for \bl{r$_1$} and \bl{r$_2$}. |
283 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip |
237 \item \bl{$P$} holds for \bl{r$^*$} under the assumption that \bl{$P$} already |
284 \item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already |
238 holds for \bl{r}. |
285 holds for \bl{$r$}. |
239 \end{itemize} |
286 \end{itemize} |
240 |
287 |
241 \end{frame}} |
288 \end{frame}} |
242 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
289 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
243 |
290 |
244 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
291 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
245 \mode<presentation>{ |
292 \mode<presentation>{ |
246 \begin{frame}[c] |
293 \begin{frame}[c] |
247 \frametitle{\begin{tabular}{c}Proofs about Natural Numbers\\ and Strings\end{tabular}} |
294 \frametitle{\begin{tabular}{c}Proofs about Natural\\[-1mm] Numbers and Strings\end{tabular}} |
248 |
295 |
249 \begin{itemize} |
296 \begin{itemize} |
250 \item \bl{$P$} holds for \bl{$0$} and |
297 \item \bl{$P$} holds for \bl{$0$} and |
251 \item \bl{$P$} holds for \bl{$n + 1$} under the assumption that \bl{$P$} already |
298 \item \bl{$P$} holds for \bl{$n + 1$} under the assumption that \bl{$P$} already |
252 holds for \bl{$n$} |
299 holds for \bl{$n$} |
253 \end{itemize}\bigskip |
300 \end{itemize}\bigskip |
254 |
301 |
255 \begin{itemize} |
302 \begin{itemize} |
256 \item \bl{$P$} holds for \bl{\texttt{""}} and |
303 \item \bl{$P$} holds for \bl{$""$} and |
257 \item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already |
304 \item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already |
258 holds for \bl{$s$} |
305 holds for \bl{$s$} |
259 \end{itemize} |
306 \end{itemize} |
260 |
307 |
261 \end{frame}} |
308 \end{frame}} |
262 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
309 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
263 |
310 |
264 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
265 \mode<presentation>{ |
|
266 \begin{frame}[t] |
|
267 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
|
268 |
|
269 \begin{center} |
|
270 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
|
271 \bl{r} & \bl{$::=$} & \bl{$\varnothing$} & null\\ |
|
272 & \bl{$\mid$} & \bl{$\epsilon$} & empty string / "" / []\\ |
|
273 & \bl{$\mid$} & \bl{c} & character\\ |
|
274 & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$} & sequence\\ |
|
275 & \bl{$\mid$} & \bl{r$_1$ + r$_2$} & alternative / choice\\ |
|
276 & \bl{$\mid$} & \bl{r$^*$} & star (zero or more)\\ |
|
277 \end{tabular}\bigskip\pause |
|
278 \end{center} |
|
279 |
|
280 \end{frame}} |
|
281 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
282 |
|
283 |
|
284 |
311 |
285 |
312 |
286 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
313 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
287 \mode<presentation>{ |
314 \mode<presentation>{ |
288 \begin{frame}[c] |
315 \begin{frame}[c] |
289 \frametitle{\begin{tabular}{c}Languages\end{tabular}} |
316 \frametitle{\begin{tabular}{c}Languages\end{tabular}} |
290 |
317 |
291 A \alert{language} is a set of strings.\bigskip |
318 A \alert{language} is a set of strings.\bigskip |
292 |
319 |
293 A \alert{regular expression} specifies a set of strings or language.\bigskip |
320 A \alert{regular expression} specifies a language.\bigskip |
294 |
321 |
295 A language is \alert{regular} iff there exists |
322 A language is \alert{regular} iff there exists |
296 a regular expression that recognises all its strings.\bigskip\bigskip\pause |
323 a regular expression that recognises all its strings.\bigskip\bigskip\pause |
297 |
324 |
298 \textcolor{gray}{not all languages are regular, e.g.~\bl{a$^n$b$^n$}.} |
325 \textcolor{gray}{not all languages are regular, e.g.~\bl{a$^n$b$^n$}.} |