30 Office: & S1.27 (1st floor Strand Building)\\ |
30 Office: & S1.27 (1st floor Strand Building)\\ |
31 Slides: & KEATS (also home work is there)\\ |
31 Slides: & KEATS (also home work is there)\\ |
32 \end{tabular} |
32 \end{tabular} |
33 \end{center} |
33 \end{center} |
34 \end{frame} |
34 \end{frame} |
35 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
35 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
36 |
36 |
37 |
37 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
38 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
39 \mode<presentation>{ |
|
40 \begin{frame}[c] |
38 \begin{frame}[c] |
41 \frametitle{Regexps and Automata} |
39 \frametitle{Regexps and Automata} |
42 |
40 |
43 \begin{center} |
41 \begin{center} |
44 \begin{tikzpicture} |
42 \begin{tikzpicture} |
45 \node (rexp) {\bl{\bf Regexps}}; |
43 \node (rexp) {\bl{\bf Regexps}}; |
46 \node (nfa) [right=of rexp] {\bl{\bf NFAs}}; |
44 \node (nfa) [right=of rexp] {\bl{\bf NFAs}}; |
47 \node (dfa) [right=of nfa] {\bl{\bf DFAs}}; |
45 \node (dfa) [right=of nfa] {\bl{\bf DFAs}}; |
48 \onslide<3->{\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}};} |
46 \node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}}; |
49 \path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa); |
47 \path[->,red, line width=2mm] (rexp) edge node [above=4mm, black] |
50 \path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa); |
48 {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa); |
51 \onslide<3->{\path[->, red, line width=2mm] (dfa) edge node [below=9mm, black] {minimisation} (mdfa);} |
49 \path[->,red, line width=2mm] (nfa) edge node [above=4mm, black] |
52 \onslide<2->{\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp);} |
50 {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa); |
|
51 \path[->, red, line width=2mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa); |
|
52 \path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp); |
53 \end{tikzpicture}\\ |
53 \end{tikzpicture}\\ |
54 \end{center} |
54 \end{center} |
55 |
55 |
56 \end{frame}} |
56 \end{frame} |
57 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
57 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
58 |
58 |
59 |
59 |
60 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
60 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
61 \mode<presentation>{ |
61 \begin{frame}[t] |
62 \begin{frame}[t] |
62 \frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}} |
63 \frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}} |
63 |
64 |
64 \mbox{}\\[-13mm] |
65 \begin{tikzpicture} |
65 |
66 \begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs}, |
66 \begin{tikzpicture}[y=.2cm, x=.09cm] |
67 enlargelimits=false, |
67 %axis |
68 xtick={0,5,...,30}, |
68 \draw (0,0) -- coordinate (x axis mid) (100,0); |
69 xmax=30, |
69 \draw (0,0) -- coordinate (y axis mid) (0,30); |
70 ymax=35, |
70 %ticks |
71 ytick={0,5,...,30}, |
71 \foreach \x in {0,10,...,100} |
72 scaled ticks=false, |
72 \draw (\x,1pt) -- (\x,-3pt) |
73 axis lines=left, |
73 node[anchor=north] {\x}; |
74 width=10cm, |
74 \foreach \y in {0,5,...,30} |
75 height=7cm, |
75 \draw (1pt,\y) -- (-3pt,\y) |
76 legend entries={Python,Ruby,my NFA}, |
76 node[anchor=east] {\y}; |
77 legend pos=north west, |
77 %labels |
78 legend cell align=left] |
78 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
79 \addplot[blue,mark=*, mark options={fill=white}] |
79 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
80 table {re-python.data}; |
80 |
81 \addplot[brown,mark=pentagon*, mark options={fill=white}] |
81 %plots |
82 table {re-ruby.data}; |
82 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
83 \addplot[red,mark=triangle*, mark options={fill=white}] |
83 file {re-python.data}; |
84 table {nfasearch.data}; |
84 \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
85 \end{axis} |
85 file {nfa.data}; |
|
86 \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] |
|
87 file {re-ruby.data}; |
|
88 |
|
89 |
|
90 %legend |
|
91 \begin{scope}[shift={(4,20)}] |
|
92 \draw[color=blue] (0,0) -- |
|
93 plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
94 node[right]{\small Python}; |
|
95 \draw[yshift=-\baselineskip, color=brown] (0,0) -- |
|
96 plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
97 node[right]{\small Ruby}; |
|
98 \draw[yshift=\baselineskip, color=red] (0,0) -- |
|
99 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
100 node[right]{\small NFA 1}; |
|
101 \end{scope} |
|
102 \end{tikzpicture} |
|
103 |
|
104 \end{frame} |
|
105 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
106 |
|
107 |
|
108 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
109 \mode<presentation>{ |
|
110 \begin{frame}[t] |
|
111 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
|
112 |
|
113 \mbox{}\\[-13mm] |
|
114 |
|
115 \begin{tikzpicture}[y=.2cm, x=.3cm] |
|
116 %axis |
|
117 \draw (0,0) -- coordinate (x axis mid) (30,0); |
|
118 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
119 %ticks |
|
120 \foreach \x in {0,5,...,30} |
|
121 \draw (\x,1pt) -- (\x,-3pt) |
|
122 node[anchor=north] {\x}; |
|
123 \foreach \y in {0,5,...,30} |
|
124 \draw (1pt,\y) -- (-3pt,\y) |
|
125 node[anchor=east] {\y}; |
|
126 %labels |
|
127 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
|
128 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
129 |
|
130 %plots |
|
131 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
|
132 file {re-python.data}; |
|
133 \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
134 file {nfasearch.data}; |
|
135 \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] |
|
136 file {re-ruby.data}; |
|
137 |
|
138 %legend |
|
139 \begin{scope}[shift={(4,20)}] |
|
140 \draw[color=blue] (0,0) -- |
|
141 plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
142 node[right]{\small Python}; |
|
143 \draw[yshift=-\baselineskip, color=brown] (0,0) -- |
|
144 plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
145 node[right]{\small Ruby}; |
|
146 \draw[yshift=\baselineskip, color=red] (0,0) -- |
|
147 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
148 node[right]{\small NFA 2}; |
|
149 \end{scope} |
|
150 \end{tikzpicture} |
86 \end{tikzpicture} |
151 |
87 |
152 \end{frame}} |
88 \end{frame}} |
153 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
89 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
154 |
90 |
155 |
91 |
156 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
92 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
157 \mode<presentation>{ |
93 \begin{frame}[c] |
158 \begin{frame}<2>[c] |
|
159 \frametitle{DFA to Rexp} |
94 \frametitle{DFA to Rexp} |
160 |
95 |
161 \begin{center} |
96 \begin{center} |
162 \begin{tikzpicture}[scale=2, line width=0.5mm] |
97 \begin{tikzpicture}[scale=2,>=stealth',very thick, |
163 \only<1>{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
98 every state/.style={minimum size=0pt, |
164 \only<2->{\node[state, initial,accepting] (q0) at ( 0,1) {$q_0$};} |
99 draw=blue!50,very thick,fill=blue!20},] |
165 \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};} |
100 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
166 \only<2->{\node[state,accepting] (q1) at ( 1,1) {$q_1$};} |
101 \node[state] (q1) at ( 1,1) {$q_1$}; |
167 \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};} |
102 \node[state, accepting] (q2) at ( 2,1) {$q_2$}; |
168 \only<2->{\node[state] (q2) at ( 2,1) {$q_2$};} |
103 \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) |
169 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
104 (q1) edge[bend left] node[above] {\alert{$b$}} (q0) |
170 (q1) edge[bend left] node[above] {$b$} (q0) |
105 (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) |
171 (q2) edge[bend left=50] node[below] {$b$} (q0) |
106 (q1) edge node[above] {\alert{$a$}} (q2) |
172 (q1) edge node[above] {$a$} (q2) |
107 (q2) edge [loop right] node {\alert{$a$}} () |
173 (q2) edge [loop right] node {$a$} () |
108 (q0) edge [loop below] node {\alert{$b$}} (); |
174 (q0) edge [loop below] node {$b$} () |
|
175 ; |
|
176 \end{tikzpicture} |
|
177 \end{center} |
|
178 |
|
179 \onslide<3>{How to get from a DFA to a regular expression?} |
|
180 |
|
181 \end{frame}} |
|
182 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
183 |
|
184 |
|
185 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
186 \mode<presentation>{ |
|
187 \begin{frame}[c] |
|
188 |
|
189 \begin{center} |
|
190 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
191 \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
|
192 \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
193 \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
194 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
|
195 (q1) edge[bend left] node[above] {$b$} (q0) |
|
196 (q2) edge[bend left=50] node[below] {$b$} (q0) |
|
197 (q1) edge node[above] {$a$} (q2) |
|
198 (q2) edge [loop right] node {$a$} () |
|
199 (q0) edge [loop below] node {$b$} () |
|
200 ; |
|
201 \end{tikzpicture} |
|
202 \end{center}\pause\bigskip |
|
203 |
|
204 \onslide<2->{ |
|
205 \begin{center} |
|
206 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
|
207 \bl{$q_0$} & \bl{$=$} & \bl{$2\, q_0 + 3 \,q_1 + 4\, q_2$}\\ |
|
208 \bl{$q_1$} & \bl{$=$} & \bl{$2 \,q_0 + 3\, q_1 + 1\, q_2$}\\ |
|
209 \bl{$q_2$} & \bl{$=$} & \bl{$1\, q_0 + 5\, q_1 + 2\, q_2$}\\ |
|
210 |
|
211 \end{tabular} |
|
212 \end{center} |
|
213 } |
|
214 |
|
215 \end{frame}} |
|
216 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
217 |
|
218 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
219 \mode<presentation>{ |
|
220 \begin{frame}[c] |
|
221 |
|
222 \begin{center} |
|
223 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
224 \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
|
225 \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
226 \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
227 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
|
228 (q1) edge[bend left] node[above] {$b$} (q0) |
|
229 (q2) edge[bend left=50] node[below] {$b$} (q0) |
|
230 (q1) edge node[above] {$a$} (q2) |
|
231 (q2) edge [loop right] node {$a$} () |
|
232 (q0) edge [loop below] node {$b$} () |
|
233 ; |
|
234 \end{tikzpicture} |
109 \end{tikzpicture} |
235 \end{center}\bigskip |
110 \end{center}\bigskip |
236 |
111 |
237 \onslide<2->{ |
112 \begin{center} |
238 \begin{center} |
113 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l} |
239 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
114 \bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b + q_2\,b$} & (start state)\\ |
240 \bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b + q_2\,b$}\\ |
|
241 \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ |
115 \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ |
242 \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ |
116 \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ |
243 |
117 |
244 \end{tabular} |
118 \end{tabular} |
245 \end{center} |
119 \end{center} |
|
120 |
|
121 \onslide<2->{ |
|
122 Arden's Lemma: |
|
123 \begin{center} |
|
124 If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} |
|
125 \end{center} |
246 } |
126 } |
247 |
127 |
248 \onslide<3->{ |
128 \end{frame} |
249 Arden's Lemma: |
|
250 \begin{center} |
|
251 If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} |
|
252 \end{center} |
|
253 } |
|
254 |
|
255 \end{frame}} |
|
256 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
129 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
257 |
130 |
258 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
131 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
259 \mode<presentation>{ |
132 \mode<presentation>{ |
260 \begin{frame}[c] |
133 \begin{frame}[c] |
354 \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
227 \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
355 \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
228 \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
356 \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
229 \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
357 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); |
230 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); |
358 \end{tikzpicture} |
231 \end{tikzpicture} |
359 \end{center} |
232 & |
|
233 \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm] |
|
234 \draw (0,0) -- (4,0); |
|
235 \draw (0,1) -- (4,1); |
|
236 \draw (0,2) -- (3,2); |
|
237 \draw (0,3) -- (2,3); |
|
238 \draw (0,4) -- (1,4); |
|
239 |
|
240 \draw (0,0) -- (0, 4); |
|
241 \draw (1,0) -- (1, 4); |
|
242 \draw (2,0) -- (2, 3); |
|
243 \draw (3,0) -- (3, 2); |
|
244 \draw (4,0) -- (4, 1); |
|
245 |
|
246 \draw (0.5,-0.5) node {$q_0$}; |
|
247 \draw (1.5,-0.5) node {$q_1$}; |
|
248 \draw (2.5,-0.5) node {$q_2$}; |
|
249 \draw (3.5,-0.5) node {$q_3$}; |
|
250 |
|
251 \draw (-0.5, 3.5) node {$q_1$}; |
|
252 \draw (-0.5, 2.5) node {$q_2$}; |
|
253 \draw (-0.5, 1.5) node {$q_3$}; |
|
254 \draw (-0.5, 0.5) node {$q_4$}; |
|
255 |
|
256 \draw (0.5,0.5) node {\large$\star$}; |
|
257 \draw (1.5,0.5) node {\large$\star$}; |
|
258 \draw (2.5,0.5) node {\large$\star$}; |
|
259 \draw (3.5,0.5) node {\large$\star$}; |
|
260 \draw (0.5,1.5) node {\large$\star$}; |
|
261 \draw (2.5,1.5) node {\large$\star$}; |
|
262 \draw (0.5,3.5) node {\large$\star$}; |
|
263 \draw (1.5,2.5) node {\large$\star$}; |
|
264 \end{tikzpicture}} |
|
265 \end{tabular} |
|
266 \end{center} |
|
267 |
360 |
268 |
361 \mbox{}\\[-20mm]\mbox{} |
269 \mbox{}\\[-20mm]\mbox{} |
362 |
270 |
363 \begin{center} |
271 \begin{center} |
364 \begin{tikzpicture}[>=stealth',very thick,auto, |
272 \begin{tikzpicture}[>=stealth',very thick,auto, |
376 \end{center} |
284 \end{center} |
377 |
285 |
378 \end{frame} |
286 \end{frame} |
379 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
287 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
380 |
288 |
381 |
289 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
382 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
290 \begin{frame}[c] |
383 \mode<presentation>{ |
291 \frametitle{Alternatives} |
384 \begin{frame}<1-2>[c] |
292 \mbox{}\\[-17mm]\mbox{} |
385 |
293 |
386 \begin{center} |
294 \begin{center} |
387 \begin{tikzpicture}[>=stealth',very thick,auto, |
295 \begin{tikzpicture}[>=stealth',very thick,auto, |
388 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
296 every state/.style={minimum size=0pt, |
389 \node[state,initial] (q_0) {$q_0$}; |
297 inner sep=2pt,draw=blue!50,very thick,fill=blue!20}] |
|
298 \only<1>{\node[state,initial] (q_0) {$q_0$};} |
|
299 \only<2->{\node[state,accepting] (q_0) {$q_0$};} |
390 \node[state] (q_1) [right=of q_0] {$q_1$}; |
300 \node[state] (q_1) [right=of q_0] {$q_1$}; |
391 \node[state] (q_2) [below right=of q_0] {$q_2$}; |
301 \node[state] (q_2) [below right=of q_0] {$q_2$}; |
392 \node[state] (q_3) [right=of q_2] {$q_3$}; |
302 \node[state] (q_3) [right=of q_2] {$q_3$}; |
393 \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; |
303 \only<1>{\node[state, accepting] (q_4) [right=of q_1] {$q_4$};} |
|
304 \only<2->{\node[state, initial right] (q_4) [right=of q_1] {$q_4$};} |
|
305 \only<1-2>{ |
394 \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); |
306 \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); |
395 \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); |
307 \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); |
396 \path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); |
308 \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); |
397 \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); |
309 \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); |
398 \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); |
310 \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); |
399 \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
311 \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
400 \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
312 \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
401 \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
313 \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
402 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); |
314 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);} |
403 \end{tikzpicture} |
315 \only<3->{ |
404 \end{center}\pause |
316 \path[<-] (q_0) edge node [above] {\alert{$a$}} (q_1); |
405 |
317 \path[<-] (q_1) edge node [above] {\alert{$a$}} (q_4); |
406 \mbox{}\\[-20mm]\mbox{} |
318 \path[<-] (q_4) edge [loop above] node {\alert{$a, b$}} (); |
407 |
319 \path[<-] (q_3) edge node [right] {\alert{$a$}} (q_4); |
408 \begin{center} |
320 \path[<-] (q_2) edge node [above] {\alert{$a$}} (q_3); |
409 \begin{tikzpicture}[>=stealth',very thick,auto, |
321 \path[<-] (q_1) edge node [right] {\alert{$b$}} (q_2); |
410 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
322 \path[<-] (q_0) edge node [above] {\alert{$b$}} (q_2); |
411 \node[state,initial] (q_02) {$q_{0, 2}$}; |
323 \path[<-] (q_2) edge [loop left] node {\alert{$b$}} (); |
412 \node[state] (q_13) [right=of q_02] {$q_{1, 3}$}; |
324 \path[<-] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);} |
413 \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$}; |
325 \end{tikzpicture} |
414 \path[->] (q_02) edge [bend left] node [above] {\alert{$a$}} (q_13); |
326 \end{center} |
415 \path[->] (q_13) edge [bend left] node [below] {\alert{$b$}} (q_02); |
327 \mbox{}\\[-18mm] |
416 \path[->] (q_02) edge [loop below] node {\alert{$b$}} (); |
|
417 \path[->] (q_13) edge node [above] {\alert{$a$}} (q_4); |
|
418 \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); |
|
419 \end{tikzpicture}\\ |
|
420 minimal automaton |
|
421 \end{center} |
|
422 |
|
423 \end{frame}} |
|
424 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
425 |
|
426 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
427 \mode<presentation>{ |
|
428 \begin{frame}[c] |
|
429 |
328 |
430 \begin{itemize} |
329 \begin{itemize} |
431 \item Assuming you have the alphabet \bl{$\{a, b, c\}$}\bigskip |
330 \item<2-> exchange initial / accepting states |
432 \item Give a regular expression that can recognise all strings that have at least one \bl{$b$}. |
331 \item<3-> reverse all edges |
|
332 \item<4-> subset construction $\Rightarrow$ DFA |
|
333 \item<5-> repeat once more \onslide<6->{$\Rightarrow$ minimal DFA} |
433 \end{itemize} |
334 \end{itemize} |
434 |
335 |
435 \end{frame}} |
336 \end{frame} |
436 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
337 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
437 |
338 |
|
339 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
340 \begin{frame}[c] |
|
341 \frametitle{Regular Languages} |
|
342 |
|
343 Two equivalent definitions:\bigskip |
|
344 |
|
345 \begin{quote}\rm A language is \alert{regular} iff there exists a |
|
346 regular expression that recognises all its strings. |
|
347 \end{quote} |
|
348 |
|
349 \begin{quote}\rm A language is \alert{regular} iff there exists an |
|
350 automaton that recognises all its strings. |
|
351 \end{quote}\bigskip\bigskip |
|
352 |
|
353 |
|
354 \small |
|
355 for example $a^nb^n$ is not regular |
|
356 \end{frame} |
|
357 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
358 |
|
359 |
|
360 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
361 \begin{frame}[c] |
|
362 \frametitle{Negation} |
|
363 |
|
364 Regular languages are closed under negation:\bigskip |
|
365 |
|
366 \begin{center} |
|
367 \begin{tikzpicture}[scale=2,>=stealth',very thick, |
|
368 every state/.style={minimum size=0pt, |
|
369 draw=blue!50,very thick,fill=blue!20}] |
|
370 \only<1>{\node[state,initial] (q0) at ( 0,1) {$q_0$};} |
|
371 \only<2>{\node[state,initial,accepting] (q0) at ( 0,1) {$q_0$};} |
|
372 \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
373 \only<2>{\node[state,accepting] (q1) at ( 1,1) {$q_1$};} |
|
374 \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};} |
|
375 \only<2>{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
376 \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) |
|
377 (q1) edge[bend left] node[above] {\alert{$b$}} (q0) |
|
378 (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) |
|
379 (q1) edge node[above] {\alert{$a$}} (q2) |
|
380 (q2) edge [loop right] node {\alert{$a$}} () |
|
381 (q0) edge [loop below] node {\alert{$b$}} (); |
|
382 \end{tikzpicture} |
|
383 \end{center}\bigskip\bigskip |
|
384 |
|
385 \onslide<2>{But requires that the automaton is \alert{completed}!} |
|
386 |
|
387 \end{frame} |
|
388 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
389 |
|
390 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
391 \begin{frame}[c] |
|
392 |
|
393 \mbox{\lstinputlisting[language=While]{../progs/fib.while}} |
|
394 |
|
395 \end{frame} |
|
396 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
397 |
|
398 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
399 \begin{frame}[c] |
|
400 \frametitle{??} |
|
401 |
|
402 \mbox{\lstinputlisting[language=While]{../progs/collatz.while}} |
|
403 |
|
404 \end{frame} |
|
405 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
406 |
|
407 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
408 \begin{frame}[c] |
|
409 \frametitle{A Compiler} |
|
410 |
|
411 \begin{tikzpicture}[scale=1] |
|
412 \draw[line width=1mm] (-0.3, 0) rectangle (1.5,2); |
|
413 \draw[line width=1mm] (-1.8, 0) rectangle (-3.6,2); |
|
414 \draw (4.4,1) node {Code Gen}; |
|
415 \draw (0.6,1.7) node {\small Parser}; |
|
416 \draw (-2.7,1.7) node {\small Lexer}; |
|
417 |
|
418 \draw[red,->,line width = 2mm] (1.7,1) -- (3.2,1); |
|
419 \draw[red,<-,line width = 2mm] (-0.6,1) -- (-1.6,1); |
|
420 \draw[red,<-,line width = 2mm] (-3.8,1) -- (-4.8,1); |
|
421 |
|
422 \draw (-4.6,1.7) node {\small string}; |
|
423 \draw (-1.1,1.7) node {\small tokens}; |
|
424 \draw ( 2.3,1.7) node {\small AST}; |
|
425 \end{tikzpicture} |
|
426 |
|
427 \end{frame} |
|
428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
429 |
|
430 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
431 \begin{frame}[t] |
|
432 |
|
433 \tt |
|
434 \begin{center}\large |
|
435 \code{"if true then then 42 else +"} |
|
436 \end{center} |
|
437 |
|
438 |
|
439 \begin{tabular}{@{}l} |
|
440 KEYWORD: \\ |
|
441 \hspace{5mm}{if}, {then}, {else},\\ |
|
442 WHITESPACE:\\ |
|
443 \hspace{5mm}{" "}, {$\backslash$n},\\ |
|
444 IDENT:\\ |
|
445 \hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + {\_})$^*$\\ |
|
446 NUM:\\ |
|
447 \hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {0}\\ |
|
448 OP:\\ |
|
449 \hspace{5mm}{+}\\ |
|
450 COMMENT:\\ |
|
451 \hspace{5mm}{$\slash$*} $\cdot$ (ALL$^*$ $\cdot$ {$\sim$(*$\slash$)} $\cdot$ ALL$^*$) $\cdot$ {*$\slash$} |
|
452 \end{tabular} |
|
453 |
|
454 \end{frame} |
|
455 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
456 |
|
457 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
458 \begin{frame}[t] |
|
459 |
|
460 \tt |
|
461 \begin{center}\large |
|
462 \code{"if true then then 42 else +"} |
|
463 \end{center} |
|
464 |
|
465 \only<1>{ |
|
466 \small\begin{tabular}{l} |
|
467 KEYWORD(if),\\ |
|
468 WHITESPACE,\\ |
|
469 IDENT(true),\\ |
|
470 WHITESPACE,\\ |
|
471 KEYWORD(then),\\ |
|
472 WHITESPACE,\\ |
|
473 KEYWORD(then),\\ |
|
474 WHITESPACE,\\ |
|
475 NUM(42),\\ |
|
476 WHITESPACE,\\ |
|
477 KEYWORD(else),\\ |
|
478 WHITESPACE,\\ |
|
479 OP(+) |
|
480 \end{tabular}} |
|
481 |
|
482 \only<2>{ |
|
483 \small\begin{tabular}{l} |
|
484 KEYWORD(if),\\ |
|
485 IDENT(true),\\ |
|
486 KEYWORD(then),\\ |
|
487 KEYWORD(then),\\ |
|
488 NUM(42),\\ |
|
489 KEYWORD(else),\\ |
|
490 OP(+) |
|
491 \end{tabular}} |
|
492 |
|
493 \end{frame} |
|
494 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
495 |
|
496 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
497 \begin{frame}[c] |
|
498 |
|
499 |
|
500 There is one small problem with the tokenizer. How should we |
|
501 tokenize: |
|
502 |
|
503 \begin{center} |
|
504 \large\code{"x-3"} |
|
505 \end{center} |
|
506 |
|
507 \tt |
|
508 \begin{tabular}{@{}l} |
|
509 ID: \ldots\\ |
|
510 OP:\\ |
|
511 \hspace{5mm}\texttt{"+"}, \texttt{"-"}\\ |
|
512 NUM:\\ |
|
513 \hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {''0''}\\ |
|
514 NUMBER:\\ |
|
515 \hspace{5mm}NUM + (\texttt{"-"} $\cdot$ NUM)\\ |
|
516 \end{tabular} |
|
517 |
|
518 \end{frame} |
|
519 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
520 |
|
521 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
522 \begin{frame}[c] |
|
523 \frametitle{POSIX: Two Rules} |
|
524 |
|
525 \begin{itemize} |
|
526 \item Longest match rule (``maximal munch rule''): The |
|
527 longest initial substring matched by any regular expression is taken |
|
528 as next token.\bigskip |
|
529 |
|
530 \item Rule priority: |
|
531 For a particular longest initial substring, the first regular |
|
532 expression that can match determines the token. |
|
533 \end{itemize}\bigskip\bigskip\pause |
|
534 |
|
535 \small |
|
536 \hfill most posix matchers are buggy\\ |
|
537 \footnotesize |
|
538 \hfill \url{http://www.haskell.org/haskellwiki/Regex_Posix} |
|
539 |
|
540 %\url{http://www.technologyreview.com/tr10/?year=2011} |
|
541 %finite deterministic automata/ nondeterministic automaton |
|
542 %\item problem with infix operations, for example i-12 |
|
543 |
|
544 \end{frame} |
|
545 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
546 |
|
547 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
548 \begin{frame}[c] |
|
549 \frametitle{Sulzmann Matcher} |
|
550 |
|
551 We want to match the string \bl{$abc$} using \bl{$r_1$}: |
|
552 |
|
553 \begin{center} |
|
554 \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] |
|
555 \node (r1) {\bl{$r_1$}}; |
|
556 \node (r2) [right=of r1] {\bl{$r_2$}}; |
|
557 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};\pause |
|
558 \node (r3) [right=of r2] {\bl{$r_3$}}; |
|
559 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};\pause |
|
560 \node (r4) [right=of r3] {\bl{$r_4$}}; |
|
561 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};\pause |
|
562 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};\pause |
|
563 \node (v4) [below=of r4] {\bl{$v_4$}}; |
|
564 \draw[->,line width=1mm] (r4) -- (v4);\pause |
|
565 \node (v3) [left=of v4] {\bl{$v_3$}}; |
|
566 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};\pause |
|
567 \node (v2) [left=of v3] {\bl{$v_2$}}; |
|
568 \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};\pause |
|
569 \node (v1) [left=of v2] {\bl{$v_1$}}; |
|
570 \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};\pause |
|
571 \draw[->,line width=0.5mm] (r3) -- (v3); |
|
572 \draw[->,line width=0.5mm] (r2) -- (v2); |
|
573 \draw[->,line width=0.5mm] (r1) -- (v1); |
|
574 \end{tikzpicture} |
|
575 \end{center} |
|
576 |
|
577 \end{frame} |
|
578 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
438 |
579 |
439 \end{document} |
580 \end{document} |
440 |
581 |
441 %%% Local Variables: |
582 %%% Local Variables: |
442 %%% mode: latex |
583 %%% mode: latex |