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