48 \end{itemize} |
48 \end{itemize} |
49 |
49 |
50 \end{frame} |
50 \end{frame} |
51 %%%%%%%%%%% |
51 %%%%%%%%%%% |
52 |
52 |
53 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
54 \begin{frame}[c] |
|
55 \frametitle{Regular Expressions} |
|
56 |
|
57 In programming languages they are often used to recognise:\medskip |
|
58 |
|
59 \begin{itemize} |
|
60 \item symbols, digits |
|
61 \item identifiers |
|
62 \item numbers (non-leading zeros) |
|
63 \item keywords |
|
64 \item comments |
|
65 \end{itemize}\bigskip |
|
66 |
|
67 \mbox{}\hfill\bl{\url{http://www.regexper.com}} |
|
68 \end{frame} |
|
69 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
70 |
53 |
71 |
54 |
72 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
55 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
73 \begin{frame}[c] |
56 \begin{frame}[c] |
74 \frametitle{Last Week} |
57 \frametitle{Last Week} |
148 |
131 |
149 \end{frame} |
132 \end{frame} |
150 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
133 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
151 |
134 |
152 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
135 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
153 \begin{frame}[c] |
136 \begin{frame}[t] |
154 \frametitle{Simplification} |
137 \frametitle{Simplification} |
155 |
138 |
156 Given \bl{$r \dn ((a \cdot b) + b)^*$} what is |
139 Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows |
157 |
140 |
158 \begin{center} |
141 \begin{center} |
159 \def\arraystretch{2} |
142 \def\arraystretch{2} |
160 \begin{tabular}{@{}lcl} |
143 \begin{tabular}{@{}lcl} |
161 \bl{$((\ONE \cdot b) + \ZERO) \cdot r$} |
144 \bl{$((\ONE \cdot b) + \ZERO) \cdot r$} |
295 |
278 |
296 A \alert{\bf deterministic finite automaton}, DFA, consists of: |
279 A \alert{\bf deterministic finite automaton}, DFA, consists of: |
297 |
280 |
298 \begin{itemize} |
281 \begin{itemize} |
299 \item an alphabet \bl{$\varSigma$} |
282 \item an alphabet \bl{$\varSigma$} |
300 \item a set of states \bl{$\mbox{Q}$} |
283 \item a set of states \bl{$\mbox{Qs}$} |
301 \item one of these states is the start state \bl{$\mbox{Q}_0$} |
284 \item one of these states is the start state \bl{$\mbox{Q}_0$} |
302 \item some states are accepting states \bl{$F$}, and |
285 \item some states are accepting states \bl{$F$}, and |
303 \item there is transition function \bl{$\delta$}\bigskip |
286 \item there is transition function \bl{$\delta$}\bigskip |
304 |
287 |
305 \small |
288 \small |
306 which takes a state as argument and a character and produces a |
289 which takes a state as argument and a character and produces a |
307 new state; this function might not be everywhere defined $\Rightarrow$ partial function |
290 new state; this function might not be everywhere defined $\Rightarrow$ partial function |
308 \end{itemize} |
291 \end{itemize} |
309 |
292 |
310 \begin{center} |
293 \begin{center} |
311 \bl{$A(\varSigma, \mbox{Q}, \mbox{Q}_0, F, \delta)$} |
294 \bl{$A(\varSigma, \mbox{Qs}, \mbox{Q}_0, F, \delta)$} |
312 \end{center} |
295 \end{center} |
313 |
296 |
314 \end{frame} |
297 \end{frame} |
315 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
298 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
316 |
299 |
472 \end{tikzpicture} |
455 \end{tikzpicture} |
473 \end{center} |
456 \end{center} |
474 |
457 |
475 \end{frame} |
458 \end{frame} |
476 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
459 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
460 |
|
461 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
462 \begin{frame}[c] |
|
463 \frametitle{Another Example} |
|
464 |
|
465 For the regular expression \bl{$(.^*)a\,(.^{\{n\}})bc$}\bigskip\bigskip |
|
466 |
|
467 % \begin{center} |
|
468 \mbox{}\hspace{-11mm} |
|
469 \begin{tikzpicture}[>=stealth',very thick, auto, |
|
470 every state/.style={minimum size=5pt,inner sep=1pt, |
|
471 draw=blue!50,very thick,fill=blue!20},scale=1, node distance=5mm, |
|
472 decoration={brace,mirror,amplitude=7}] |
|
473 \node[state,initial] (Q_0) {$\;0\;$}; |
|
474 \node[state] (Q_1) [right=of Q_0] {$\;1\;$}; |
|
475 \node[state] (Q_2) [right=of Q_1] {$\;2\;$}; |
|
476 \node (Q_3) [right=of Q_2] {$\hspace{-1mm}\ldots\hspace{-3mm}$}; |
|
477 \node[state] (Q_4) [right=of Q_3] {$\;\phantom{1}\;$}; |
|
478 \node (Q_5) [right=of Q_4] {$\hspace{-1mm}\ldots\hspace{-3mm}$}; |
|
479 \node[state] (Q_6) [right=of Q_5] {\tiny$n+1$}; |
|
480 \node[state] (Q_7) [right=of Q_6] {\tiny$n+2$}; |
|
481 \node[state,accepting] (Q_8) [right=of Q_7] {\tiny$n+3$}; |
|
482 |
|
483 \path[->] (Q_0) edge [loop above] node {$*$} (); |
|
484 \path[->] (Q_0) edge node [above] {$a$} (Q_1); |
|
485 \path[->] (Q_1) edge node [above] {$*$} (Q_2); |
|
486 \path[->] (Q_2) edge node [above] {$*$} (Q_3); |
|
487 \path[->] (Q_4) edge node [above] {$*$} (Q_5); |
|
488 \path[->] (Q_5) edge node [above] {$*$} (Q_6); |
|
489 \path[->] (Q_6) edge node [above] {$b$} (Q_7); |
|
490 \path[->] (Q_7) edge node [above] {$c$} (Q_8); |
|
491 |
|
492 \draw [decorate] ([yshift=-5mm]Q_1.east) --node[below=3mm]{$n$} ([yshift=-5mm]Q_6.west); |
|
493 \end{tikzpicture}\bigskip |
|
494 |
|
495 |
|
496 {\small Note the star-transitions: accept any character.} |
|
497 |
|
498 \end{frame} |
477 |
499 |
478 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
500 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
479 \begin{frame}[c] |
501 \begin{frame}[c] |
480 \frametitle{Two Epsilon NFA Examples} |
502 \frametitle{Two Epsilon NFA Examples} |
481 |
503 |