22 \\[-3mm] |
23 \\[-3mm] |
23 \LARGE Compilers and \\[-2mm] |
24 \LARGE Compilers and \\[-2mm] |
24 \LARGE Formal Languages (3)\\[3mm] |
25 \LARGE Formal Languages (3)\\[3mm] |
25 \end{tabular}} |
26 \end{tabular}} |
26 |
27 |
27 \normalsize |
28 \normalsize |
28 \begin{center} |
29 \begin{center} |
29 \begin{tabular}{lp{8cm}} |
30 \begin{tabular}{ll} |
30 Email: & christian.urban at kcl.ac.uk\\ |
31 Email: & christian.urban at kcl.ac.uk\\ |
31 Office: & N\liningnums{7.07} (North Wing, Bush House)\\ |
32 Office Hours: & Thursdays 12 -- 14\\ |
32 Slides: & KEATS (also homework and coursework is there)\\ |
33 Location: & N7.07 (North Wing, Bush House)\\ |
|
34 Slides \& Progs: & KEATS (also homework is there)\\ |
33 \end{tabular} |
35 \end{tabular} |
34 \end{center} |
36 \end{center} |
35 |
37 |
36 \end{frame} |
38 \end{frame} |
37 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
39 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
149 \end{center} |
151 \end{center} |
150 |
152 |
151 \end{frame} |
153 \end{frame} |
152 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
154 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
153 |
155 |
154 |
156 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
157 \begin{frame}[c] |
|
158 \frametitle{Proofs about Rexp} |
|
159 |
|
160 \begin{itemize} |
|
161 \item \bl{$P$} holds for \bl{$\ZERO$}, \bl{$\ONE$} and \bl{c}\bigskip |
|
162 \item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already |
|
163 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip |
|
164 \item \bl{$P$} holds for \bl{$r_1 \cdot r_2$} under the assumption that \bl{$P$} already |
|
165 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip |
|
166 \item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already |
|
167 holds for \bl{$r$}. |
|
168 \end{itemize} |
|
169 |
|
170 \end{frame} |
|
171 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
172 |
155 |
173 |
156 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
157 \begin{frame}[c] |
175 \begin{frame}[c] |
158 |
176 |
159 We proved |
177 We proved |
165 by induction on the regular expression \bl{$r$}.\bigskip\pause |
183 by induction on the regular expression \bl{$r$}.\bigskip\pause |
166 |
184 |
167 \begin{center} |
185 \begin{center} |
168 {\huge\bf\alert{Any Questions?}} |
186 {\huge\bf\alert{Any Questions?}} |
169 \end{center} |
187 \end{center} |
170 |
|
171 \end{frame} |
|
172 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
173 |
|
174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
175 \begin{frame}[c] |
|
176 |
|
177 We need to prove |
|
178 |
|
179 \begin{center} |
|
180 \bl{$L(der\,c\,r) = Der\,c\,(L(r))$} |
|
181 \end{center} |
|
182 |
|
183 also by induction on the regular expression \bl{$r$}. |
|
184 \end{frame} |
|
185 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
186 |
|
187 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
188 \begin{frame}[c] |
|
189 \frametitle{Proofs about Rexps} |
|
190 |
|
191 \begin{itemize} |
|
192 \item \bl{$P$} holds for \bl{$\ZERO$}, \bl{$\ONE$} and \bl{c}\bigskip |
|
193 \item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already |
|
194 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip |
|
195 \item \bl{$P$} holds for \bl{$r_1 \cdot r_2$} under the assumption that \bl{$P$} already |
|
196 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip |
|
197 \item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already |
|
198 holds for \bl{$r$}. |
|
199 \end{itemize} |
|
200 |
188 |
201 \end{frame} |
189 \end{frame} |
202 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
190 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
203 |
191 |
204 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
192 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
218 \end{itemize} |
206 \end{itemize} |
219 |
207 |
220 \end{frame} |
208 \end{frame} |
221 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
209 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
222 |
210 |
|
211 |
|
212 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
213 \begin{frame}[c] |
|
214 \frametitle{Correctness Proof \\[-1mm] |
|
215 for our Matcher} |
|
216 |
|
217 \begin{itemize} |
|
218 \item We started from |
|
219 |
|
220 \begin{center} |
|
221 \begin{tabular}{rp{4cm}} |
|
222 & \bl{$s \in L(r)$}\medskip\\ |
|
223 \bl{$\Leftrightarrow$} & \bl{$[] \in \Ders\,s\,(L(r))$}\pause |
|
224 \end{tabular} |
|
225 \end{center}\bigskip |
|
226 |
|
227 \item \textbf{\alert{if}} we can show \bl{$\Ders\, s\,(L(r)) = L(\ders\,s\,r)$} we |
|
228 have\bigskip |
|
229 |
|
230 \begin{center} |
|
231 \begin{tabular}{rp{4cm}} |
|
232 \bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\ |
|
233 \bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\ |
|
234 \bl{$\dn$} & \bl{$matches\,s\,r$} |
|
235 \end{tabular} |
|
236 \end{center} |
|
237 |
|
238 \end{itemize} |
|
239 |
|
240 \end{frame} |
|
241 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
242 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
243 \begin{frame}[c] |
|
244 |
|
245 We need to prove |
|
246 |
|
247 \begin{center} |
|
248 \bl{$L(der\,c\,r) = Der\,c\,(L(r))$} |
|
249 \end{center} |
|
250 |
|
251 also by induction on the regular expression \bl{$r$}. |
|
252 \end{frame} |
|
253 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
254 |
|
255 |
|
256 |
223 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
257 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
224 \begin{frame}[t] |
258 \begin{frame}[t] |
225 \frametitle{Regular Expressions} |
259 \frametitle{(Basic) Regular Expressions} |
226 |
260 |
227 \begin{center} |
261 \begin{center} |
228 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
262 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
229 \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & nothing\\ |
263 \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & nothing\\ |
230 & \bl{$\mid$} & \bl{$\ONE$} & empty string / "" / $[]$\\ |
264 & \bl{$\mid$} & \bl{$\ONE$} & empty string / "" / $[]$\\ |
236 \end{center} |
270 \end{center} |
237 |
271 |
238 How about ranges \bl{$[a\mbox{-}z]$}, \bl{$r^+$} and \bl{$\sim{}r$}? Do they increase the |
272 How about ranges \bl{$[a\mbox{-}z]$}, \bl{$r^+$} and \bl{$\sim{}r$}? Do they increase the |
239 set of languages we can recognise? |
273 set of languages we can recognise? |
240 |
274 |
241 \end{frame} |
|
242 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
243 |
|
244 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
245 \begin{frame}[c] |
|
246 \frametitle{Negation of Regular Expr's} |
|
247 |
|
248 \begin{itemize} |
|
249 \item \bl{$\sim{}r$} \hspace{6mm} (everything that \bl{$r$} cannot recognise)\medskip |
|
250 \item \bl{$L(\sim{}r) \dn UNIV - L(r)$}\medskip |
|
251 \item \bl{$nullable (\sim{}r) \dn not\, (nullable(r))$}\medskip |
|
252 \item \bl{$der\,c\,(\sim{}r) \dn \;\sim{}(der\,c\,r)$} |
|
253 \end{itemize}\bigskip\pause |
|
254 |
|
255 Used often for recognising comments: |
|
256 |
|
257 \[ |
|
258 \bl{/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /} |
|
259 \] |
|
260 |
|
261 \end{frame} |
275 \end{frame} |
262 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
276 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
263 |
277 |
264 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
278 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
265 \begin{frame}[c] |
279 \begin{frame}[c] |
546 \end{tikzpicture}\\\\ |
560 \end{tikzpicture}\\\\ |
547 \raisebox{1mm}{\bl{$\ONE$}} & |
561 \raisebox{1mm}{\bl{$\ONE$}} & |
548 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
562 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
549 \node[state, initial, accepting] (Q_0) {$\mbox{}$}; |
563 \node[state, initial, accepting] (Q_0) {$\mbox{}$}; |
550 \end{tikzpicture}\\\\ |
564 \end{tikzpicture}\\\\ |
551 \raisebox{2mm}{\bl{$c$}} & |
565 \raisebox{5mm}{\bl{$c$}} & |
552 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
566 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
553 \node[state, initial] (Q_0) {$\mbox{}$}; |
567 \node[state, initial] (Q_0) {$\mbox{}$}; |
554 \node[state, accepting] (Q_1) [right=of Q_0] {$\mbox{}$}; |
568 \node[state, accepting] (Q_1) [right=of Q_0] {$\mbox{}$}; |
555 \path[->] (Q_0) edge node [below] {\alert{$c$}} (Q_1); |
569 \path[->] (Q_0) edge node [below] {\alert{$c$}} (Q_1); |
556 \end{tikzpicture}\\\\ |
570 \end{tikzpicture}\\\\ |