# HG changeset patch # User Christian Urban # Date 1506519980 -3600 # Node ID fdbc7d0ec04f5098ea460b9310db015c80f2d89f # Parent 12a8f57f68ea1148162e5064a2afd77c53704a7c updated diff -r 12a8f57f68ea -r fdbc7d0ec04f handouts/ho01.pdf Binary file handouts/ho01.pdf has changed diff -r 12a8f57f68ea -r fdbc7d0ec04f handouts/ho01.tex --- a/handouts/ho01.tex Tue Sep 26 14:38:45 2017 +0100 +++ b/handouts/ho01.tex Wed Sep 27 14:46:20 2017 +0100 @@ -632,7 +632,7 @@ shown via automata. Even sombody who has written a 700+-page book\footnote{\url{http://goo.gl/fD0eHx}} on regular exprssions did not know better. Well, we showed it can also be -done with regular expressions only.\footnote{\url{http://www.inf.kcl.ac.uk/staff/urbanc/Publications/rexp.pdf}} +done with regular expressions only.\footnote{\url{http://nms.kcl.ac.uk/christian.urban/Publications/posix.pdf}} What a feeling when you are an outsider to the subject! To conclude: Despite my early ignorance about regular expressions, I diff -r 12a8f57f68ea -r fdbc7d0ec04f hws/hw01.pdf Binary file hws/hw01.pdf has changed diff -r 12a8f57f68ea -r fdbc7d0ec04f hws/hw01.tex --- a/hws/hw01.tex Tue Sep 26 14:38:45 2017 +0100 +++ b/hws/hw01.tex Wed Sep 27 14:46:20 2017 +0100 @@ -56,7 +56,7 @@ the strings in $A$ is the empty string, for example $A = \{[a], [b], [c], []\}$. -\item (1)How many basic regular expressions are there to match +\item (1) How many basic regular expressions are there to match the string $abcd$? (2) How many if they cannot include $\ONE$ and $\ZERO$? (3) How many if they are also not allowed to contain stars? (4) How many if they are also diff -r 12a8f57f68ea -r fdbc7d0ec04f slides/slides01.pdf Binary file slides/slides01.pdf has changed diff -r 12a8f57f68ea -r fdbc7d0ec04f slides/slides01.tex --- a/slides/slides01.tex Tue Sep 26 14:38:45 2017 +0100 +++ b/slides/slides01.tex Wed Sep 27 14:46:20 2017 +0100 @@ -33,9 +33,9 @@ \end{tabular}} \begin{center} - \includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm} - \includegraphics[scale=0.31]{pics/ante2.jpg}\\ - \footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)} + %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm} + %\includegraphics[scale=0.31]{pics/ante2.jpg}\\ + %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)} \end{center} \normalsize @@ -656,7 +656,7 @@ \begin{bubble}[10cm] \large -A regular expression \bl{$r$} matches a string \bl{$s$} +A regular expression \bl{$r$} matches a string~\bl{$s$} provided \begin{center} diff -r 12a8f57f68ea -r fdbc7d0ec04f slides/slides02.pdf Binary file slides/slides02.pdf has changed diff -r 12a8f57f68ea -r fdbc7d0ec04f slides/slides02.tex --- a/slides/slides02.tex Tue Sep 26 14:38:45 2017 +0100 +++ b/slides/slides02.tex Wed Sep 27 14:46:20 2017 +0100 @@ -223,6 +223,52 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] +\frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] + Regular Expression\end{tabular}} + +\begin{textblock}{15}(1,4) + \begin{tabular}{rcl} + \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ + \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ + \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ + \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ + \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\ + \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star \quad\dn \bigcup_{0 \le n} L(r)^n$}\\ + \end{tabular} +\end{textblock} + +\begin{textblock}{6}(9,12)\small +\bl{$L$} is a function from regular expressions to +sets of strings\\ +\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{\begin{tabular}{c}The Specification\\ of Matching\end{tabular}} + +\begin{bubble}[10cm] +\large +A regular expression \bl{$r$} matches a string~\bl{$s$} +provided + +\begin{center} +\bl{$s \in L(r)$}\\ +\end{center} +\end{bubble}\bigskip\bigskip + +\ldots and the point of the this lecture is +to decide this problem as fast as possible +(unlike Python, Ruby, Java etc) + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] \frametitle{Semantic Derivative} \begin{itemize} @@ -283,42 +329,6 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}} - -\begin{textblock}{15}(1,4) - \begin{tabular}{@ {}rcl} - \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ - \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ - \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ - \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ - \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ - \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star$}\\ - \end{tabular} -\end{textblock} - -\begin{textblock}{6}(9,12)\small -\bl{$L$} is a function from regular expressions to -sets of strings\\ -\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} -\end{textblock} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - -\large -\begin{center} -What is \bl{$L(a^*)$}? -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{\begin{tabular}{c} diff -r 12a8f57f68ea -r fdbc7d0ec04f slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r 12a8f57f68ea -r fdbc7d0ec04f slides/slides04.pdf Binary file slides/slides04.pdf has changed diff -r 12a8f57f68ea -r fdbc7d0ec04f slides/slides05.pdf Binary file slides/slides05.pdf has changed diff -r 12a8f57f68ea -r fdbc7d0ec04f slides/slides06.pdf Binary file slides/slides06.pdf has changed diff -r 12a8f57f68ea -r fdbc7d0ec04f slides/slides07.pdf Binary file slides/slides07.pdf has changed diff -r 12a8f57f68ea -r fdbc7d0ec04f slides/slides08.pdf Binary file slides/slides08.pdf has changed diff -r 12a8f57f68ea -r fdbc7d0ec04f slides/slides09.pdf Binary file slides/slides09.pdf has changed