1 \documentclass[dvipsnames,14pt,t]{beamer} |
1 \documentclass[dvipsnames,14pt,t]{beamer} |
2 \usepackage{beamerthemeplaincu} |
2 \usepackage{../slides} |
3 \usepackage[absolute,overlay]{textpos} |
3 \usepackage{../graphics} |
4 \usepackage{ifthen} |
|
5 \usepackage{tikz} |
|
6 \usepackage{pgf} |
|
7 \usepackage{calc} |
|
8 \usepackage{ulem} |
|
9 \usepackage{courier} |
|
10 \usepackage{listings} |
|
11 \renewcommand{\uline}[1]{#1} |
|
12 \usetikzlibrary{arrows} |
|
13 \usetikzlibrary{automata} |
|
14 \usetikzlibrary{shapes} |
|
15 \usetikzlibrary{shadows} |
|
16 \usetikzlibrary{positioning} |
|
17 \usetikzlibrary{calc} |
|
18 \usetikzlibrary{fit} |
|
19 \usetikzlibrary{backgrounds} |
|
20 \usepackage{graphicx} |
|
21 \usepackage{../langs} |
4 \usepackage{../langs} |
22 \usepackage{../data} |
5 \usepackage{../data} |
23 |
6 |
24 \makeatletter |
7 \hfuzz=220pt |
25 \lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}} |
8 |
26 \@empty\z@\@empty |
9 \pgfplotsset{compat=1.11} |
27 \makeatother |
10 |
|
11 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
28 |
12 |
29 % beamer stuff |
13 % beamer stuff |
30 \renewcommand{\slidecaption}{AFL 03, King's College London, 9.~October 2013} |
14 \renewcommand{\slidecaption}{AFL 03, King's College London} |
31 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
|
32 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions |
|
33 |
15 |
34 \begin{document} |
16 \begin{document} |
35 |
17 |
36 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
18 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
37 \mode<presentation>{ |
19 \begin{frame}[t] |
38 \begin{frame}<1>[t] |
|
39 \frametitle{% |
20 \frametitle{% |
40 \begin{tabular}{@ {}c@ {}} |
21 \begin{tabular}{@ {}c@ {}} |
41 \\[-3mm] |
22 \\[-3mm] |
42 \LARGE Automata and \\[-2mm] |
23 \LARGE Automata and \\[-2mm] |
43 \LARGE Formal Languages (3)\\[3mm] |
24 \LARGE Formal Languages (3)\\[3mm] |
44 \end{tabular}} |
25 \end{tabular}} |
45 |
|
46 %\begin{center} |
|
47 %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm} |
|
48 %\includegraphics[scale=0.31]{pics/ante2.jpg}\\ |
|
49 %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)} |
|
50 %\end{center} |
|
51 |
26 |
52 \normalsize |
27 \normalsize |
53 \begin{center} |
28 \begin{center} |
54 \begin{tabular}{lp{8cm}} |
29 \begin{tabular}{lp{8cm}} |
55 Email: & christian.urban at kcl.ac.uk\\ |
30 Email: & christian.urban at kcl.ac.uk\\ |
56 Office: & S1.27 (1st floor Strand Building)\\ |
31 Office: & S1.27 (1st floor Strand Building)\\ |
57 Slides: & KEATS (also home work and coursework is there)\\ |
32 Slides: & KEATS (also home work and coursework is there)\\ |
58 \end{tabular} |
33 \end{tabular} |
59 \end{center} |
34 \end{center} |
60 |
35 |
61 |
36 \end{frame} |
62 \end{frame}} |
|
63 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
37 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
64 |
38 |
65 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
39 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
66 \mode<presentation>{ |
|
67 \begin{frame}[c] |
40 \begin{frame}[c] |
68 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
41 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
69 |
42 |
70 In programming languages they are often used to recognise:\medskip |
43 In programming languages they are often used to recognise:\medskip |
71 |
44 |
75 \item numbers (non-leading zeros) |
48 \item numbers (non-leading zeros) |
76 \item keywords |
49 \item keywords |
77 \item comments |
50 \item comments |
78 \end{itemize}\bigskip |
51 \end{itemize}\bigskip |
79 |
52 |
80 |
|
81 \mbox{}\hfill\bl{\url{http://www.regexper.com}} |
53 \mbox{}\hfill\bl{\url{http://www.regexper.com}} |
82 \end{frame}} |
54 \end{frame} |
83 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
55 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
84 |
56 |
85 |
57 |
86 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
58 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
87 \mode<presentation>{ |
59 \begin{frame}[c] |
88 \begin{frame}[c] |
60 \frametitle{Last Week} |
89 \frametitle{\begin{tabular}{c}Last Week\end{tabular}} |
|
90 |
61 |
91 Last week I showed you a regular expression matcher |
62 Last week I showed you a regular expression matcher |
92 which works provably correctly in all cases. |
63 which works provably correct in all cases (we did not |
93 |
64 do the proving part though) |
94 \begin{center} |
65 |
95 \bl{$matcher\,r\,s$} \;\;if and only if \;\; \bl{$s \in L(r)$} |
66 \begin{center} |
|
67 \bl{$matches\,r\,s$} \;\;if and only if \;\; \bl{$s \in L(r)$} |
96 \end{center}\bigskip\bigskip |
68 \end{center}\bigskip\bigskip |
97 |
69 |
98 \small |
70 \small |
99 \textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)} |
71 \textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)} |
100 |
72 |
101 |
73 \end{frame} |
102 \end{frame}} |
74 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
103 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
75 |
104 |
76 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
105 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
77 \begin{frame}[c] |
106 \mode<presentation>{ |
78 \frametitle{The Derivative of a Rexp} |
107 \begin{frame}[c] |
|
108 \frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}} |
|
109 |
79 |
110 \begin{center} |
80 \begin{center} |
111 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
81 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
112 \bl{$der\, c\, (\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
82 \bl{$der\, c\, (\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
113 \bl{$der\, c\, (\epsilon)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
83 \bl{$der\, c\, (\epsilon)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
114 \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\ |
84 \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\ |
115 \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\ |
85 \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\ |
116 \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ |
86 \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ |
117 & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ |
87 & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ |
118 & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\ |
88 & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\ |
119 \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\smallskip\\ |
89 \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\ |
120 |
90 |
121 \bl{$der\!s\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ |
91 \bl{$\textit{ders}\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ |
122 \bl{$der\!s\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\ |
92 \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\ |
123 \end{tabular} |
93 \end{tabular} |
124 \end{center} |
94 \end{center} |
125 |
95 |
126 |
96 \end{frame} |
127 \end{frame}} |
97 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
128 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
98 |
129 |
99 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
130 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
100 \begin{frame}[c] |
131 \mode<presentation>{ |
|
132 \begin{frame}[c] |
|
133 |
|
134 |
101 |
135 To see what is going on, define |
102 To see what is going on, define |
136 |
103 |
137 \begin{center} |
104 \begin{center} |
138 \bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } |
105 \bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } |
139 \end{center}\bigskip\bigskip |
106 \end{center}\bigskip\bigskip |
140 |
107 |
141 \small |
108 For \bl{$A = \{\textit{foo}, \textit{bar}, \textit{frak}\}$} then |
142 For \bl{$A = \{"f\!oo", "bar", "f\!rak"\}$} then |
|
143 |
109 |
144 \begin{center} |
110 \begin{center} |
145 \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} |
111 \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} |
146 $Der\,f\,A$ & $=$ & $\{"oo", "rak"\}$\\ |
112 $Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\ |
147 $Der\,b\,A$ & $=$ & $\{"ar"\}$\\ |
113 $Der\,b\,A$ & $=$ & $\{\textit{ar}\}$\\ |
148 $Der\,a\,A$ & $=$ & $\varnothing$\\ |
114 $Der\,a\,A$ & $=$ & $\varnothing$\\ |
149 \end{tabular}} |
115 \end{tabular}} |
150 \end{center} |
116 \end{center} |
151 |
117 |
152 |
118 \end{frame} |
153 \end{frame}} |
119 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
154 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
120 |
155 |
121 |
156 |
122 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
157 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
123 \begin{frame}[c] |
158 \mode<presentation>{ |
124 \frametitle{The Idea of the Algorithm} |
159 \begin{frame}[c] |
125 |
160 \frametitle{\begin{tabular}{c}The Idea of the Algorithm\end{tabular}} |
126 If we want to recognise the string \bl{$abc$} with regular expression \bl{$r$} |
161 |
|
162 If we want to recognise the string \bl{$"abc"$} with regular expression \bl{$r$} |
|
163 then\medskip |
127 then\medskip |
164 |
128 |
165 \begin{enumerate} |
129 \begin{enumerate} |
166 \item \bl{$Der\,a\,(L(r))$}\pause |
130 \item \bl{$Der\,a\,(L(r))$}\pause |
167 \item \bl{$Der\,b\,(Der\,a\,(L(r)))$}\pause |
131 \item \bl{$Der\,b\,(Der\,a\,(L(r)))$}\pause |
168 \item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r))))$}\pause |
132 \item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r))))$}\bigskip\pause |
169 \item finally we test whether the empty string is in this set\pause\medskip |
133 \item finally we test whether the empty string is in this set\pause\medskip |
170 \end{enumerate} |
134 \end{enumerate} |
171 |
135 |
172 The matching algorithm works similarly, just over regular expression instead of sets. |
136 The matching algorithm works similarly, just over regular expressions instead of sets. |
173 \end{frame}} |
137 \end{frame} |
174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
138 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
175 |
139 |
176 |
140 |
177 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
141 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
178 \mode<presentation>{ |
142 \begin{frame}[c] |
179 \begin{frame}[c] |
143 |
180 |
144 Input: string \bl{$abc$} and regular expression \bl{$r$} |
181 Input: string \bl{$"abc"$} and regular expression \bl{$r$} |
|
182 |
145 |
183 \begin{enumerate} |
146 \begin{enumerate} |
184 \item \bl{$der\,a\,r$} |
147 \item \bl{$der\,a\,r$} |
185 \item \bl{$der\,b\,(der\,a\,r)$} |
148 \item \bl{$der\,b\,(der\,a\,r)$} |
186 \item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause |
149 \item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause |
187 \item finally check whether the last regular expression can match the empty string |
150 \item finally check whether the last regular expression can match the empty string |
188 \end{enumerate} |
151 \end{enumerate} |
189 |
152 |
190 \end{frame}} |
153 \end{frame} |
191 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
154 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
192 |
155 |
193 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
156 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
194 \mode<presentation>{ |
|
195 \begin{frame}[c] |
157 \begin{frame}[c] |
196 |
158 |
197 We proved already |
159 We proved already |
198 |
160 |
199 \begin{center} |
161 \begin{center} |
200 \bl{$nullable(r)$} \;if and only if\; \bl{$"" \in L(r)$} |
162 \bl{$nullable(r)$} \;if and only if\; \bl{$[] \in L(r)$} |
201 \end{center} |
163 \end{center} |
202 |
164 |
203 by induction on the regular expression.\bigskip\pause |
165 by induction on the regular expression.\bigskip\pause |
204 |
166 |
205 \begin{center} |
167 \begin{center} |
206 \huge\bf \alert{Any Questions?} |
168 {\huge\bf\alert{Any Questions?}} |
207 \end{center} |
169 \end{center} |
208 |
170 |
209 |
171 \end{frame} |
210 \end{frame}} |
172 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
211 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
173 |
212 |
174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
213 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
214 \mode<presentation>{ |
|
215 \begin{frame}[c] |
175 \begin{frame}[c] |
216 |
176 |
217 We need to prove |
177 We need to prove |
218 |
178 |
219 \begin{center} |
179 \begin{center} |
220 \bl{$L(der\,c\,r) = Der\,c\,(L(r))$} |
180 \bl{$L(der\,c\,r) = Der\,c\,(L(r))$} |
221 \end{center} |
181 \end{center} |
222 |
182 |
223 by induction on the regular expression. |
183 by induction on the regular expression. |
224 \end{frame}} |
184 \end{frame} |
225 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
185 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
226 |
186 |
227 |
187 |
228 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
188 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
229 \mode<presentation>{ |
189 \begin{frame}[c] |
230 \begin{frame}[c] |
190 \frametitle{Proofs about Rexps} |
231 \frametitle{\begin{tabular}{c}Proofs about Rexps\end{tabular}} |
|
232 |
191 |
233 \begin{itemize} |
192 \begin{itemize} |
234 \item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip |
193 \item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip |
235 \item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already |
194 \item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already |
236 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip |
195 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip |
238 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip |
197 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip |
239 \item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already |
198 \item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already |
240 holds for \bl{$r$}. |
199 holds for \bl{$r$}. |
241 \end{itemize} |
200 \end{itemize} |
242 |
201 |
243 \end{frame}} |
202 \end{frame} |
244 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
203 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
245 |
204 |
246 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
205 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
247 \mode<presentation>{ |
|
248 \begin{frame}[c] |
206 \begin{frame}[c] |
249 \frametitle{\begin{tabular}{c}Proofs about Natural\\[-1mm] Numbers and Strings\end{tabular}} |
207 \frametitle{\begin{tabular}{c}Proofs about Natural\\[-1mm] Numbers and Strings\end{tabular}} |
250 |
208 |
251 \begin{itemize} |
209 \begin{itemize} |
252 \item \bl{$P$} holds for \bl{$0$} and |
210 \item \bl{$P$} holds for \bl{$0$} and |
253 \item \bl{$P$} holds for \bl{$n + 1$} under the assumption that \bl{$P$} already |
211 \item \bl{$P$} holds for \bl{$n + 1$} under the assumption that \bl{$P$} already |
254 holds for \bl{$n$} |
212 holds for \bl{$n$} |
255 \end{itemize}\bigskip |
213 \end{itemize}\bigskip |
256 |
214 |
257 \begin{itemize} |
215 \begin{itemize} |
258 \item \bl{$P$} holds for \bl{$""$} and |
216 \item \bl{$P$} holds for \bl{$[]$} and |
259 \item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already |
217 \item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already |
260 holds for \bl{$s$} |
218 holds for \bl{$s$} |
261 \end{itemize} |
219 \end{itemize} |
262 |
220 |
263 \end{frame}} |
221 \end{frame} |
264 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
222 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
265 |
223 |
266 |
224 |
267 |
225 |
268 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
226 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
269 \mode<presentation>{ |
227 \begin{frame}[c] |
270 \begin{frame}[c] |
228 \frametitle{Languages} |
271 \frametitle{\begin{tabular}{c}Languages\end{tabular}} |
|
272 |
229 |
273 A \alert{language} is a set of strings.\bigskip |
230 A \alert{language} is a set of strings.\bigskip |
274 |
231 |
275 A \alert{regular expression} specifies a language.\bigskip |
232 A \alert{regular expression} specifies a language.\bigskip |
276 |
233 |
277 A language is \alert{regular} iff there exists |
234 A language is \alert{regular} iff there exists |
278 a regular expression that recognises all its strings.\bigskip\bigskip\pause |
235 a regular expression that recognises all its strings.\bigskip\bigskip\pause |
279 |
236 |
280 \textcolor{gray}{not all languages are regular, e.g.~\bl{$a^nb^n$}.} |
237 \textcolor{gray}{not all languages are regular, e.g.~\bl{$a^nb^n$} is not} |
281 \end{frame}} |
238 \end{frame} |
282 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
239 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
283 |
240 |
284 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
241 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
285 \mode<presentation>{ |
|
286 \begin{frame}[t] |
242 \begin{frame}[t] |
287 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
243 \frametitle{Regular Expressions} |
288 |
244 |
289 \begin{center} |
245 \begin{center} |
290 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
246 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
291 \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$} & null\\ |
247 \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$} & null\\ |
292 & \bl{$\mid$} & \bl{$\epsilon$} & empty string / "" / $[]$\\ |
248 & \bl{$\mid$} & \bl{$\epsilon$} & empty string / "" / $[]$\\ |
319 |
274 |
320 \[ |
275 \[ |
321 \bl{/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /} |
276 \bl{/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /} |
322 \] |
277 \] |
323 |
278 |
324 |
279 \end{frame} |
325 \end{frame}} |
280 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
326 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
281 |
327 |
282 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
328 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
283 \begin{frame}[c] |
329 \mode<presentation>{ |
284 \frametitle{Negation} |
330 \begin{frame}[c] |
285 |
331 \frametitle{\begin{tabular}{c}Negation\end{tabular}} |
286 Assume you have an alphabet consisting of the letters \bl{$a$}, \bl{$b$} and \bl{$c$} only. |
332 |
287 Find a (basic!) regular expression that matches all strings \emph{\alert{except}} |
333 Assume you have an alphabet consisting of the letters \bl{a}, \bl{b} and \bl{c} only. |
288 \bl{$ab$} and \bl{$ac$}! |
334 Find a regular expression that matches all strings \emph{except} \bl{ab} and \bl{ac}. |
289 |
335 |
290 \end{frame} |
336 \end{frame}} |
291 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
337 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
292 |
338 |
293 |
339 |
294 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
340 |
295 %\mode<presentation>{ |
341 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
296 %\begin{frame}[c] |
342 \mode<presentation>{ |
297 %\frametitle{\begin{tabular}{c}Regular Exp's for Lexing\end{tabular}} |
343 \begin{frame}[c] |
298 % |
344 \frametitle{\begin{tabular}{c}Regular Exp's for Lexing\end{tabular}} |
299 %Lexing separates strings into ``words'' / components. |
345 |
300 % |
346 Lexing separates strings into ``words'' / components. |
301 %\begin{itemize} |
347 |
302 %\item Identifiers (non-empty strings of letters or digits, starting with a letter) |
348 \begin{itemize} |
303 %\item Numbers (non-empty sequences of digits omitting leading zeros) |
349 \item Identifiers (non-empty strings of letters or digits, starting with a letter) |
304 %\item Keywords (else, if, while, \ldots) |
350 \item Numbers (non-empty sequences of digits omitting leading zeros) |
305 %\item White space (a non-empty sequence of blanks, newlines and tabs) |
351 \item Keywords (else, if, while, \ldots) |
306 %\item Comments |
352 \item White space (a non-empty sequence of blanks, newlines and tabs) |
307 %\end{itemize} |
353 \item Comments |
308 % |
354 \end{itemize} |
309 %\end{frame}} |
355 |
310 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
356 \end{frame}} |
311 |
357 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
312 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
358 |
313 \begin{frame}[c] |
359 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
314 \frametitle{Automata} |
360 \mode<presentation>{ |
|
361 \begin{frame}[c] |
|
362 \frametitle{\begin{tabular}{c}Automata\end{tabular}} |
|
363 |
315 |
364 A \alert{deterministic finite automaton} consists of: |
316 A \alert{deterministic finite automaton} consists of: |
365 |
317 |
366 \begin{itemize} |
318 \begin{itemize} |
367 \item a set of states |
319 \item a set of states |
368 \item one of these states is the start state |
320 \item one of these states is the start state |
369 \item some states are accepting states, and |
321 \item some states are accepting states, and |
370 \item there is transition function\medskip |
322 \item there is transition function\medskip |
371 |
323 |
372 \small |
324 \small |
373 which takes a state as argument and a character and produces a new state\smallskip\\ |
325 which takes a state as argument and a character and produces a |
|
326 new state\smallskip\\ |
374 this function might not be everywhere defined |
327 this function might not be everywhere defined |
375 \end{itemize} |
328 \end{itemize} |
376 |
329 |
377 \begin{center} |
330 \begin{center} |
378 \bl{$A(Q, q_0, F, \delta)$} |
331 \bl{$A(Q, q_0, F, \delta)$} |
379 \end{center} |
332 \end{center} |
380 |
333 |
381 \end{frame}} |
334 \end{frame} |
382 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
335 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
383 |
336 |
384 |
337 |
385 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
338 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
386 \mode<presentation>{ |
|
387 \begin{frame}[c] |
339 \begin{frame}[c] |
388 |
340 |
389 \begin{center} |
341 \begin{center} |
390 \begin{tikzpicture}[>=stealth',very thick,auto, |
342 \begin{tikzpicture}[>=stealth',very thick,auto, |
391 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
343 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
770 |
733 |
771 Why is every finite set of strings a regular language? |
734 Why is every finite set of strings a regular language? |
772 \end{frame}} |
735 \end{frame}} |
773 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
736 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
774 |
737 |
775 |
|
776 |
|
777 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
738 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
778 \mode<presentation>{ |
739 \mode<presentation>{ |
779 \begin{frame}<1-2>[c] |
740 \begin{frame}<2>[c] |
780 |
741 \frametitle{DFA to Rexp} |
781 \begin{center} |
742 |
782 \begin{tikzpicture}[>=stealth',very thick,auto, |
743 \begin{center} |
783 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
744 \begin{tikzpicture}[scale=2,>=stealth',very thick, |
784 \node[state,initial] (q_0) {$q_0$}; |
745 every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] |
785 \node[state] (q_1) [right=of q_0] {$q_1$}; |
746 \only<1>{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
786 \node[state] (q_2) [below right=of q_0] {$q_2$}; |
747 \only<2->{\node[state, initial,accepting] (q0) at ( 0,1) {$q_0$};} |
787 \node[state] (q_3) [right=of q_2] {$q_3$}; |
748 \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};} |
788 \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; |
749 \only<2->{\node[state,accepting] (q1) at ( 1,1) {$q_1$};} |
789 \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); |
750 \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};} |
790 \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); |
751 \only<2->{\node[state] (q2) at ( 2,1) {$q_2$};} |
791 \path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); |
752 \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) |
792 \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); |
753 (q1) edge[bend left] node[above] {\alert{$b$}} (q0) |
793 \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); |
754 (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) |
794 \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
755 (q1) edge node[above] {\alert{$a$}} (q2) |
795 \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
756 (q2) edge [loop right] node {\alert{$a$}} () |
796 \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
757 (q0) edge [loop below] node {\alert{$b$}} () |
797 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); |
758 ; |
798 \end{tikzpicture} |
759 \end{tikzpicture} |
799 \end{center} |
760 \end{center} |
800 |
761 |
801 \mbox{}\\[-20mm]\mbox{} |
762 \onslide<3>{How to get from a DFA to a regular expression?} |
802 |
|
803 \begin{center} |
|
804 \begin{tikzpicture}[>=stealth',very thick,auto, |
|
805 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
|
806 \node[state,initial] (q_02) {$q_{0, 2}$}; |
|
807 \node[state] (q_13) [right=of q_02] {$q_{1, 3}$}; |
|
808 \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$}; |
|
809 \path[->] (q_02) edge [bend left] node [above] {\alert{$a$}} (q_13); |
|
810 \path[->] (q_13) edge [bend left] node [below] {\alert{$b$}} (q_02); |
|
811 \path[->] (q_02) edge [loop below] node {\alert{$b$}} (); |
|
812 \path[->] (q_13) edge node [above] {\alert{$a$}} (q_4); |
|
813 \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); |
|
814 \end{tikzpicture}\\ |
|
815 minimal automaton |
|
816 \end{center} |
|
817 |
763 |
818 \end{frame}} |
764 \end{frame}} |
819 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
765 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
766 |
|
767 |
|
768 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
769 \mode<presentation>{ |
|
770 \begin{frame}[c] |
|
771 |
|
772 \begin{center} |
|
773 \begin{tikzpicture}[scale=2,>=stealth',very thick, |
|
774 every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] |
|
775 \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
|
776 \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
777 \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
778 \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) |
|
779 (q1) edge[bend left] node[above] {\alert{$b$}} (q0) |
|
780 (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) |
|
781 (q1) edge node[above] {\alert{$a$}} (q2) |
|
782 (q2) edge [loop right] node {\alert{$a$}} () |
|
783 (q0) edge [loop below] node {\alert{$b$}} () |
|
784 ; |
|
785 \end{tikzpicture} |
|
786 \end{center}\pause\bigskip |
|
787 |
|
788 \onslide<2->{ |
|
789 \begin{center} |
|
790 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
|
791 \bl{$q_0$} & \bl{$=$} & \bl{$2\, q_0 + 3 \,q_1 + 4\, q_2$}\\ |
|
792 \bl{$q_1$} & \bl{$=$} & \bl{$2 \,q_0 + 3\, q_1 + 1\, q_2$}\\ |
|
793 \bl{$q_2$} & \bl{$=$} & \bl{$1\, q_0 + 5\, q_1 + 2\, q_2$}\\ |
|
794 |
|
795 \end{tabular} |
|
796 \end{center} |
|
797 } |
|
798 |
|
799 \end{frame}} |
|
800 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
801 |
|
802 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
803 \mode<presentation>{ |
|
804 \begin{frame}[c] |
|
805 |
|
806 \begin{center} |
|
807 \begin{tikzpicture}[scale=2,>=stealth',very thick, |
|
808 every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] |
|
809 \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
|
810 \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
811 \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
812 \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) |
|
813 (q1) edge[bend left] node[above] {\alert{$b$}} (q0) |
|
814 (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) |
|
815 (q1) edge node[above] {\alert{$a$}} (q2) |
|
816 (q2) edge [loop right] node {\alert{$a$}} () |
|
817 (q0) edge [loop below] node {\alert{$b$}} () |
|
818 ; |
|
819 \end{tikzpicture} |
|
820 \end{center}\bigskip |
|
821 |
|
822 \onslide<2->{ |
|
823 \begin{center} |
|
824 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
|
825 \bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b + q_2\,b$}\\ |
|
826 \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ |
|
827 \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ |
|
828 |
|
829 \end{tabular} |
|
830 \end{center} |
|
831 } |
|
832 |
|
833 \onslide<3->{ |
|
834 Arden's Lemma: |
|
835 \begin{center} |
|
836 If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} |
|
837 \end{center} |
|
838 } |
|
839 |
|
840 \end{frame}} |
|
841 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
842 |
|
843 |
820 |
844 |
821 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
845 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
822 \mode<presentation>{ |
846 \mode<presentation>{ |
823 \begin{frame}[c] |
847 \begin{frame}[c] |
824 |
848 |