1 \documentclass[dvipsnames,14pt,t]{beamer} |
|
2 \usepackage{beamerthemeplainculight} |
|
3 \usepackage[T1]{fontenc} |
|
4 \usepackage[latin1]{inputenc} |
|
5 \usepackage{mathpartir} |
|
6 \usepackage[absolute,overlay]{textpos} |
|
7 \usepackage{ifthen} |
|
8 \usepackage{tikz} |
|
9 \usepackage{pgf} |
|
10 \usepackage{calc} |
|
11 \usepackage{ulem} |
|
12 \usepackage{courier} |
|
13 \usepackage{listings} |
|
14 \renewcommand{\uline}[1]{#1} |
|
15 \usetikzlibrary{arrows} |
|
16 \usetikzlibrary{automata} |
|
17 \usetikzlibrary{shapes} |
|
18 \usetikzlibrary{shadows} |
|
19 \usetikzlibrary{positioning} |
|
20 \usetikzlibrary{calc} |
|
21 \usepackage{graphicx} |
|
22 |
|
23 \definecolor{javared}{rgb}{0.6,0,0} % for strings |
|
24 \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments |
|
25 \definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords |
|
26 \definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc |
|
27 |
|
28 \lstset{language=Java, |
|
29 basicstyle=\ttfamily, |
|
30 keywordstyle=\color{javapurple}\bfseries, |
|
31 stringstyle=\color{javagreen}, |
|
32 commentstyle=\color{javagreen}, |
|
33 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
|
34 numbers=left, |
|
35 numberstyle=\tiny\color{black}, |
|
36 stepnumber=1, |
|
37 numbersep=10pt, |
|
38 tabsize=2, |
|
39 showspaces=false, |
|
40 showstringspaces=false} |
|
41 |
|
42 \lstdefinelanguage{scala}{ |
|
43 morekeywords={abstract,case,catch,class,def,% |
|
44 do,else,extends,false,final,finally,% |
|
45 for,if,implicit,import,match,mixin,% |
|
46 new,null,object,override,package,% |
|
47 private,protected,requires,return,sealed,% |
|
48 super,this,throw,trait,true,try,% |
|
49 type,val,var,while,with,yield}, |
|
50 otherkeywords={=>,<-,<\%,<:,>:,\#,@}, |
|
51 sensitive=true, |
|
52 morecomment=[l]{//}, |
|
53 morecomment=[n]{/*}{*/}, |
|
54 morestring=[b]", |
|
55 morestring=[b]', |
|
56 morestring=[b]""" |
|
57 } |
|
58 |
|
59 \lstset{language=Scala, |
|
60 basicstyle=\ttfamily, |
|
61 keywordstyle=\color{javapurple}\bfseries, |
|
62 stringstyle=\color{javagreen}, |
|
63 commentstyle=\color{javagreen}, |
|
64 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
|
65 numbers=left, |
|
66 numberstyle=\tiny\color{black}, |
|
67 stepnumber=1, |
|
68 numbersep=10pt, |
|
69 tabsize=2, |
|
70 showspaces=false, |
|
71 showstringspaces=false} |
|
72 |
|
73 % beamer stuff |
|
74 \renewcommand{\slidecaption}{AFL 03, King's College London, 10.~October 2012} |
|
75 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
|
76 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions |
|
77 |
|
78 \begin{document} |
|
79 |
|
80 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
81 \mode<presentation>{ |
|
82 \begin{frame}<1>[t] |
|
83 \frametitle{% |
|
84 \begin{tabular}{@ {}c@ {}} |
|
85 \\[-3mm] |
|
86 \LARGE Automata and \\[-2mm] |
|
87 \LARGE Formal Languages (3)\\[3mm] |
|
88 \end{tabular}} |
|
89 |
|
90 %\begin{center} |
|
91 %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm} |
|
92 %\includegraphics[scale=0.31]{pics/ante2.jpg}\\ |
|
93 %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)} |
|
94 %\end{center} |
|
95 |
|
96 \normalsize |
|
97 \begin{center} |
|
98 \begin{tabular}{ll} |
|
99 Email: & christian.urban at kcl.ac.uk\\ |
|
100 Of$\!$fice: & S1.27 (1st floor Strand Building)\\ |
|
101 Slides: & KEATS (also home work is there)\\ |
|
102 & \alert{\bf (I have put a temporary link in there.)}\\ |
|
103 \end{tabular} |
|
104 \end{center} |
|
105 |
|
106 |
|
107 \end{frame}} |
|
108 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
109 |
|
110 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
111 \mode<presentation>{ |
|
112 \begin{frame}[c] |
|
113 \frametitle{\begin{tabular}{c}Last Week\end{tabular}} |
|
114 |
|
115 Last week I showed you |
|
116 |
|
117 \begin{itemize} |
|
118 \item one simple-minded regular expression matcher (which however does not work in all cases), and\bigskip |
|
119 \item one which works provably in all cases |
|
120 |
|
121 \begin{center} |
|
122 \bl{matcher r s} \;\;if and only if \;\; \bl{s $\in$ $L$(r)} |
|
123 \end{center} |
|
124 \end{itemize} |
|
125 |
|
126 \end{frame}} |
|
127 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
128 |
|
129 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
130 \mode<presentation>{ |
|
131 \begin{frame}[c] |
|
132 \frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}} |
|
133 |
|
134 \begin{center} |
|
135 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
|
136 \bl{der c ($\varnothing$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
|
137 \bl{der c ($\epsilon$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
|
138 \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$)} & \\ |
|
140 \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$)}\\ |
|
142 & & \bl{else (der c r$_1$) $\cdot$ r$_2$}\\ |
|
143 \bl{der c (r$^*$)} & \bl{$\dn$} & \bl{(der c r) $\cdot$ (r$^*$)}\\ |
|
144 \end{tabular} |
|
145 \end{center} |
|
146 |
|
147 ``the regular expression after \bl{c} has been recognised'' |
|
148 |
|
149 \end{frame}} |
|
150 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
151 |
|
152 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
153 \mode<presentation>{ |
|
154 \begin{frame}[c] |
|
155 |
|
156 For this we defined the set \bl{Der c A} as |
|
157 |
|
158 \begin{center} |
|
159 \bl{Der c A $\dn$ $\{$ s $|$ c::s $\in$ A$\}$ } |
|
160 \end{center} |
|
161 |
|
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 |
|
170 \end{frame}} |
|
171 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
172 |
|
173 |
|
174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
175 \mode<presentation>{ |
|
176 \begin{frame}[c] |
|
177 \frametitle{\begin{tabular}{c}The Idea of the Algorithm\end{tabular}} |
|
178 |
|
179 If we want to recognise the string \bl{abc} with regular expression \bl{r} |
|
180 then\medskip |
|
181 |
|
182 \begin{enumerate} |
|
183 \item \bl{Der a ($L$(r))}\pause |
|
184 \item \bl{Der b (Der a ($L$(r)))} |
|
185 \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 |
|
187 \end{enumerate} |
|
188 |
|
189 The matching algorithm works similarly, just over regular expression than sets. |
|
190 \end{frame}} |
|
191 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
192 |
|
193 |
|
194 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
195 \mode<presentation>{ |
|
196 \begin{frame}[c] |
|
197 |
|
198 Input: string \bl{abc} and regular expression \bl{r} |
|
199 |
|
200 \begin{enumerate} |
|
201 \item \bl{der a r} |
|
202 \item \bl{der b (der a r)} |
|
203 \item \bl{der c (der b (der a r))}\pause |
|
204 \item finally check whether the latter regular expression can match the empty string |
|
205 \end{enumerate} |
|
206 |
|
207 \end{frame}} |
|
208 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
209 |
|
210 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
211 \mode<presentation>{ |
|
212 \begin{frame}[c] |
|
213 |
|
214 We need to prove |
|
215 |
|
216 \begin{center} |
|
217 \bl{$L$(der c r) $=$ Der c ($L$(r))} |
|
218 \end{center} |
|
219 |
|
220 by induction on the regular expression. |
|
221 |
|
222 \end{frame}} |
|
223 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
224 |
|
225 |
|
226 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
227 \mode<presentation>{ |
|
228 \begin{frame}[c] |
|
229 \frametitle{\begin{tabular}{c}Proofs about Rexp\end{tabular}} |
|
230 |
|
231 \begin{itemize} |
|
232 \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 |
|
234 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 |
|
236 holds for \bl{r$_1$} and \bl{r$_2$}. |
|
237 \item \bl{$P$} holds for \bl{r$^*$} under the assumption that \bl{$P$} already |
|
238 holds for \bl{r}. |
|
239 \end{itemize} |
|
240 |
|
241 \end{frame}} |
|
242 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
243 |
|
244 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
245 \mode<presentation>{ |
|
246 \begin{frame}[c] |
|
247 \frametitle{\begin{tabular}{c}Proofs about Natural Numbers\\ and Strings\end{tabular}} |
|
248 |
|
249 \begin{itemize} |
|
250 \item \bl{$P$} holds for \bl{$0$} and |
|
251 \item \bl{$P$} holds for \bl{$n + 1$} under the assumption that \bl{$P$} already |
|
252 holds for \bl{$n$} |
|
253 \end{itemize}\bigskip |
|
254 |
|
255 \begin{itemize} |
|
256 \item \bl{$P$} holds for \bl{\texttt{""}} and |
|
257 \item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already |
|
258 holds for \bl{$s$} |
|
259 \end{itemize} |
|
260 |
|
261 \end{frame}} |
|
262 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
263 |
|
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 |
|
285 |
|
286 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
287 \mode<presentation>{ |
|
288 \begin{frame}[c] |
|
289 \frametitle{\begin{tabular}{c}Languages\end{tabular}} |
|
290 |
|
291 A \alert{language} is a set of strings.\bigskip |
|
292 |
|
293 A \alert{regular expression} specifies a set of strings or language.\bigskip |
|
294 |
|
295 A language is \alert{regular} iff there exists |
|
296 a regular expression that recognises all its strings.\bigskip\bigskip\pause |
|
297 |
|
298 \textcolor{gray}{not all languages are regular, e.g.~\bl{a$^n$b$^n$}.} |
|
299 \end{frame}} |
|
300 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
301 |
|
302 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
303 \mode<presentation>{ |
|
304 \begin{frame}[t] |
|
305 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
|
306 |
|
307 \begin{center} |
|
308 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
|
309 \bl{r} & \bl{$::=$} & \bl{$\varnothing$} & null\\ |
|
310 & \bl{$\mid$} & \bl{$\epsilon$} & empty string / "" / []\\ |
|
311 & \bl{$\mid$} & \bl{c} & character\\ |
|
312 & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$} & sequence\\ |
|
313 & \bl{$\mid$} & \bl{r$_1$ + r$_2$} & alternative / choice\\ |
|
314 & \bl{$\mid$} & \bl{r$^*$} & star (zero or more)\\ |
|
315 \end{tabular}\bigskip |
|
316 \end{center} |
|
317 |
|
318 How about ranges \bl{[a-z]}, \bl{r$^\text{+}$} and \bl{!r}? |
|
319 |
|
320 \end{frame}} |
|
321 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
322 |
|
323 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
324 \mode<presentation>{ |
|
325 \begin{frame}[c] |
|
326 \frametitle{\begin{tabular}{c}Negation of Regular Expr's\end{tabular}} |
|
327 |
|
328 \begin{itemize} |
|
329 \item \bl{!r} \hspace{6mm} (everything that \bl{r} cannot recognise)\medskip |
|
330 \item \bl{$L$(!r) $\dn$ UNIV - $L$(r)}\medskip |
|
331 \item \bl{nullable (!r) $\dn$ not (nullable(r))}\medskip |
|
332 \item \bl{der\,c\,(!r) $\dn$ !(der\,c\,r)} |
|
333 \end{itemize} |
|
334 |
|
335 \end{frame}} |
|
336 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
337 |
|
338 |
|
339 |
|
340 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
341 \mode<presentation>{ |
|
342 \begin{frame}[c] |
|
343 \frametitle{\begin{tabular}{c}Regular Exp's for Lexing\end{tabular}} |
|
344 |
|
345 Lexing separates strings into ``words'' / components. |
|
346 |
|
347 \begin{itemize} |
|
348 \item Identifiers (non-empty strings of letters or digits, starting with a letter) |
|
349 \item Numbers (non-empty sequences of digits omitting leading zeros) |
|
350 \item Keywords (else, if, while, \ldots) |
|
351 \item White space (a non-empty sequence of blanks, newlines and tabs) |
|
352 \item Comments |
|
353 \end{itemize} |
|
354 |
|
355 \end{frame}} |
|
356 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
357 |
|
358 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
359 \mode<presentation>{ |
|
360 \begin{frame}[c] |
|
361 \frametitle{\begin{tabular}{c}Automata\end{tabular}} |
|
362 |
|
363 A deterministic finite automaton consists of: |
|
364 |
|
365 \begin{itemize} |
|
366 \item a set of states |
|
367 \item one of these states is the start state |
|
368 \item some states are accepting states, and |
|
369 \item there is transition function\medskip |
|
370 |
|
371 \small |
|
372 which takes a state as argument and a character and produces a new state\smallskip\\ |
|
373 this function might not always be defined |
|
374 \end{itemize} |
|
375 |
|
376 \end{frame}} |
|
377 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
378 |
|
379 |
|
380 \end{document} |
|
381 |
|
382 %%% Local Variables: |
|
383 %%% mode: latex |
|
384 %%% TeX-master: t |
|
385 %%% End: |
|
386 |
|