82 \begin{frame}<1>[t] |
82 \begin{frame}<1>[t] |
83 \frametitle{% |
83 \frametitle{% |
84 \begin{tabular}{@ {}c@ {}} |
84 \begin{tabular}{@ {}c@ {}} |
85 \\[-3mm] |
85 \\[-3mm] |
86 \LARGE Automata and \\[-2mm] |
86 \LARGE Automata and \\[-2mm] |
87 \LARGE Formal Languages (2)\\[-3mm] |
87 \LARGE Formal Languages (2)\\[3mm] |
88 \end{tabular}} |
88 \end{tabular}} |
89 |
89 |
90 \begin{center} |
90 %\begin{center} |
91 \includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm} |
91 %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm} |
92 \includegraphics[scale=0.31]{pics/ante2.jpg}\\ |
92 %\includegraphics[scale=0.31]{pics/ante2.jpg}\\ |
93 \footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)} |
93 %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)} |
94 \end{center} |
94 %\end{center} |
95 |
95 |
96 \normalsize |
96 \normalsize |
97 \begin{center} |
97 \begin{center} |
98 \begin{tabular}{ll} |
98 \begin{tabular}{ll} |
99 Email: & christian.urban at kcl.ac.uk\\ |
99 Email: & christian.urban at kcl.ac.uk\\ |
100 Of$\!$fice: & S1.27 (1st floor Strand Building)\\ |
100 Of$\!$fice: & S1.27 (1st floor Strand Building)\\ |
101 Slides: & KEATS |
101 Slides: & KEATS |
102 \end{tabular} |
102 \end{tabular} |
103 \end{center} |
103 \end{center} |
104 |
104 |
105 |
105 |
106 \end{frame}} |
106 \end{frame}} |
107 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
107 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
108 |
|
109 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
110 \mode<presentation>{ |
|
111 \begin{frame}[c] |
|
112 \frametitle{\begin{tabular}{c}Languages\end{tabular}} |
|
113 |
|
114 A \alert{language} is a set of strings.\bigskip |
|
115 |
|
116 A \alert{regular expression} specifies a set of strings or language. |
|
117 |
|
118 \end{frame}} |
|
119 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
108 |
120 |
109 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
121 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
110 \mode<presentation>{ |
122 \mode<presentation>{ |
111 \begin{frame}[t] |
123 \begin{frame}[t] |
112 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
124 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
128 \end{frame}} |
140 \end{frame}} |
129 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
141 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
130 |
142 |
131 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
143 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
132 \mode<presentation>{ |
144 \mode<presentation>{ |
|
145 \begin{frame}[t] |
|
146 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
|
147 |
|
148 Their implementation in Scala: |
|
149 |
|
150 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
151 \texttt{\lstinputlisting{app51.scala}}} |
|
152 |
|
153 |
|
154 \end{frame}} |
|
155 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
156 |
|
157 |
|
158 |
|
159 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
160 \mode<presentation>{ |
133 \begin{frame}[c] |
161 \begin{frame}[c] |
134 \frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}} |
162 \frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}} |
135 |
163 |
136 \begin{textblock}{15}(1,4) |
164 \begin{textblock}{15}(1,4) |
137 \begin{tabular}{@ {}rcl} |
165 \begin{tabular}{@ {}rcl} |
145 |
173 |
146 \hspace{5mm}\textcolor{gray}{$L$(r)$^0$ $\;\dn\;$ $\{$""$\}$}\\ |
174 \hspace{5mm}\textcolor{gray}{$L$(r)$^0$ $\;\dn\;$ $\{$""$\}$}\\ |
147 \textcolor{gray}{$L$(r)$^{n+1}$ $\;\dn\;$ $L$(r) @ $L$(r)$^n$} |
175 \textcolor{gray}{$L$(r)$^{n+1}$ $\;\dn\;$ $L$(r) @ $L$(r)$^n$} |
148 \end{textblock} |
176 \end{textblock} |
149 |
177 |
150 \end{frame}} |
178 \only<2->{ |
151 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
179 \begin{textblock}{5}(11,5) |
|
180 \textcolor{gray}{\small |
|
181 A @ B\\ |
|
182 \ldots you take out every string from A and |
|
183 concatenate it with every string in B |
|
184 } |
|
185 \end{textblock}} |
|
186 |
|
187 \only<3->{ |
|
188 \begin{textblock}{6}(9,12)\small |
|
189 \bl{$L$} is a function from regular expressions to sets of strings\\ |
|
190 \bl{$L$ : Rexp $\Rightarrow$ Set[String]} |
|
191 \end{textblock}} |
|
192 |
|
193 |
|
194 \end{frame}} |
|
195 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
196 |
|
197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
198 \mode<presentation>{ |
|
199 \begin{frame}[c] |
|
200 |
|
201 \large |
|
202 \begin{center} |
|
203 What is \bl{$L$(a$^*$)}? |
|
204 \end{center} |
|
205 |
|
206 \end{frame}} |
|
207 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
208 |
|
209 |
152 |
210 |
153 \newcommand{\YES}{\textcolor{gray}{yes}} |
211 \newcommand{\YES}{\textcolor{gray}{yes}} |
154 \newcommand{\NO}{\textcolor{gray}{no}} |
212 \newcommand{\NO}{\textcolor{gray}{no}} |
155 \newcommand{\FORALLR}{\textcolor{gray}{$\forall$ r.}} |
213 \newcommand{\FORALLR}{\textcolor{gray}{$\forall$ r.}} |
156 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
214 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
157 \mode<presentation>{ |
215 \mode<presentation>{ |
158 \begin{frame}[c] |
216 \begin{frame}[c] |
159 \frametitle{\begin{tabular}{c}Reg Exp Equivalences\end{tabular}} |
217 \frametitle{\begin{tabular}{c}Reg Exp Equivalences\end{tabular}} |
160 |
218 |
161 \begin{center} |
219 \begin{center} |
162 \begin{tabular}{lrcl@ {\hspace{7mm}}l} |
220 \begin{tabular}{l@ {\hspace{7mm}}rcl@ {\hspace{7mm}}l} |
163 &\bl{(a + b) + c} & \bl{$\equiv^?$} & \bl{a + (b + c)} & \onslide<2->{\YES}\\ |
221 &\bl{(a + b) + c} & \bl{$\equiv^?$} & \bl{a + (b + c)} & \onslide<2->{\YES}\\ |
164 &\bl{a + a} & \bl{$\equiv^?$} & \bl{a} & \onslide<3->{\YES}\\ |
222 &\bl{a + a} & \bl{$\equiv^?$} & \bl{a} & \onslide<3->{\YES}\\ |
165 &\bl{(a $\cdot$ b) $\cdot$ c} & \bl{$\equiv^?$} & \bl{a $\cdot$ (b $\cdot$ c)} & \onslide<4->{\YES}\\ |
223 &\bl{(a $\cdot$ b) $\cdot$ c} & \bl{$\equiv^?$} & \bl{a $\cdot$ (b $\cdot$ c)} & \onslide<4->{\YES}\\ |
166 &\bl{a $\cdot$ a} & \bl{$\equiv^?$} & \bl{a} & \onslide<5->{\NO}\\ |
224 &\bl{a $\cdot$ a} & \bl{$\equiv^?$} & \bl{a} & \onslide<5->{\NO}\\ |
167 &\bl{$\epsilon^*$} & \bl{$\equiv^?$} & \bl{$\epsilon$} & \onslide<6->{\YES}\\ |
225 &\bl{$\epsilon^*$} & \bl{$\equiv^?$} & \bl{$\epsilon$} & \onslide<6->{\YES}\\ |
203 |
261 |
204 \begin{itemize} |
262 \begin{itemize} |
205 \item given a regular expression \bl{r} and a string \bl{s}, say yes or no for whether |
263 \item given a regular expression \bl{r} and a string \bl{s}, say yes or no for whether |
206 \begin{center} |
264 \begin{center} |
207 \bl{s $\in$ $L$(r)} |
265 \bl{s $\in$ $L$(r)} |
208 \end{center}\bigskip\bigskip\pause |
266 \end{center} |
209 \only<2>{\item foo}% |
267 or not.\bigskip\bigskip\pause |
210 \only<3>{\item bar} |
268 \end{itemize}\pause |
|
269 |
|
270 \small |
|
271 \begin{itemize} |
|
272 \item Identifiers (strings of letters or digits, starting with a letter) |
|
273 \item Integers (a non-empty sequence of digits) |
|
274 \item Keywords (else, if, while, \ldots) |
|
275 \item White space (a non-empty sequence of blanks, newlines and tabs) |
211 \end{itemize} |
276 \end{itemize} |
212 |
|
213 |
|
214 \end{frame}} |
277 \end{frame}} |
215 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
278 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
216 |
279 |
217 |
280 |
218 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
281 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
295 |
358 |
296 |
359 |
297 \end{frame}} |
360 \end{frame}} |
298 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
361 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
299 |
362 |
300 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
301 \mode<presentation>{ |
|
302 \begin{frame}[c] |
|
303 \frametitle{\begin{tabular}{c}This Course\end{tabular}} |
|
304 |
|
305 We will have a look at: |
|
306 |
|
307 \begin{itemize} |
|
308 \item regular expressions / regular expression matching |
|
309 \item automata |
|
310 \item the Myhill-Nerode theorem |
|
311 \item parsing |
|
312 \item grammars |
|
313 \item a small interpreter / web browser |
|
314 \end{itemize} |
|
315 |
|
316 \end{frame}} |
|
317 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
318 |
|
319 |
|
320 |
|
321 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
322 \mode<presentation>{ |
|
323 \begin{frame}[c] |
|
324 \frametitle{\begin{tabular}{c}Exam\end{tabular}} |
|
325 |
|
326 \begin{itemize} |
|
327 \item The question ``Is this relevant for the exam?'' is not appreciated!\bigskip\\ |
|
328 |
|
329 Whatever is in the homework sheets (and is not marked optional) is relevant for the |
|
330 exam.\\ No code needs to be written. |
|
331 \end{itemize} |
|
332 |
|
333 \end{frame}} |
|
334 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
335 |
|
336 |
|
337 |
|
338 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
339 \mode<presentation>{ |
|
340 \begin{frame}[t] |
|
341 \frametitle{\begin{tabular}{c}Maps in Scala\end{tabular}} |
|
342 |
|
343 \begin{itemize} |
|
344 \item {\bf\texttt{map}} takes a function, say f, and applies it to every element of the list: |
|
345 \end{itemize} |
|
346 |
|
347 \begin{textblock}{15}(2,7) |
|
348 \fontsize{13}{14}\selectfont |
|
349 \bf\texttt{List(1, 2, 3, 4, 5, 6, 7, 8, 9)} |
|
350 \end{textblock} |
|
351 |
|
352 \begin{textblock}{15}(2,10) |
|
353 \fontsize{13}{14}\selectfont |
|
354 \bf\texttt{List(1, 4, 9, 16, 25, 36, 49, 64, 81)} |
|
355 \end{textblock} |
|
356 |
|
357 \end{frame}} |
|
358 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
359 |
|
360 |
363 |
361 \end{document} |
364 \end{document} |
362 |
365 |
363 %%% Local Variables: |
366 %%% Local Variables: |
364 %%% mode: latex |
367 %%% mode: latex |