# HG changeset patch # User Christian Urban # Date 1601025431 -3600 # Node ID e70df76926c0efd7b3bb1acb8938a34abf8026b2 # Parent 82a1315c128dede5333407288057b67c477de5bb updated diff -r 82a1315c128d -r e70df76926c0 slides/slides01.pdf Binary file slides/slides01.pdf has changed diff -r 82a1315c128d -r e70df76926c0 slides/slides01.tex --- a/slides/slides01.tex Wed Sep 23 11:34:43 2020 +0100 +++ b/slides/slides01.tex Fri Sep 25 10:17:11 2020 +0100 @@ -1053,11 +1053,36 @@ % strings, or language. \end{itemize} +\only<2>{ +\begin{textblock}{4}(10.5,8) +\small +Let + +\bl{$A = \{foo, bar\}$} \bl{$B = \{a, b\}$} +\[ +\bl{A \,@\, B = \{fooa, foob, bara, barb\}} +\] +\end{textblock}} + \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] + \frametitle{Two Corner Cases} + + \Large + \begin{center} + \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\ + \bl{$A \,@\, \{\} = \;?$} + \end{center} + + \end{frame} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] \frametitle{The Meaning of a Regex} ...all the strings a regular expression can match. @@ -1083,50 +1108,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{The Meaning of a Regex} -\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$} & \onslide<4->{\bl{$\bigcup_{0 \le n} L(r)^n$}}\\ - \end{tabular}\bigskip - -\onslide<2->{ -\hspace{5mm}\bl{$L(r)^0 \;\dn\; \{[]\}$}\\ -\bl{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}\hspace{9mm}\onslide<3->{\small\textcolor{gray}{(append on sets)}\\ -\small\hspace{5cm}\textcolor{gray}{$\{ s_1 @ s_2 \;|\; s_1\in L(r) \wedge s_2 \in L(r)^n \}$}} -} - \end{textblock} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{The Meaning of Matching} - -\begin{bubble}[10cm] -\large\bf -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 next lecture is -to decide this problem as fast as possible (unlike Python, -Ruby, Java) - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -1155,130 +1137,31 @@ \end{itemize} \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - \frametitle{Questions} - - \begin{itemize} - \item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip - - \item[] - How many strings are in \bl{$A^4$}\,? - \bigskip\medskip\pause - - - \item[] - What if \bl{$A = \{[a],[b],[c],[]\}$};\\ - how many strings are then in \bl{$A^4$}\,? - \end{itemize} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Languages (Sets of Strings)} - -\begin{itemize} - -\item A \alert{\bf Language} is a set of strings, for example\medskip -\begin{center} -\bl{$\{[], hello, foobar, a, abc\}$} -\end{center}\bigskip - -\item \alert{\bf Concatenation} for strings and languages - -\begin{center} -\begin{tabular}{rcl} -\bl{$foo\;@\;bar$} & \bl{$=$} & \bl{$foobar$}\medskip\\ -\bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$} -\end{tabular} -\end{center} -\bigskip - -\small -\item [] For example \bl{$A = \{foo, bar\}$}, \bl{$B = \{a, b\}$} - -\[ -\bl{A \,@\, B = \{fooa, foob, bara, barb\}} -\] - -\end{itemize} -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - \frametitle{Two Corner Cases} - - \Large - \begin{center} - \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\ - \bl{$A \,@\, \{\} = \;?$} - \end{center} - - \end{frame} - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{The Meaning of a Regex} - ...all the strings a regular expression can match. - -\begin{center} +\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$} & \\ - \end{tabular} -\end{center} - -\begin{textblock}{14}(1.5,13.5)\small -\bl{$L$} is a function from regular expressions to -sets of strings (languages):\smallskip\\ -\bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$} + \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$} & \onslide<2->{\bl{$\bigcup_{0 \le n} L(r)^n$}}\\ + \end{tabular}\bigskip + +%\onslide<2->{ +%\hspace{5mm}\bl{$L(r)^0 \;\dn\; \{[]\}$}\\ +%\bl{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}\hspace{9mm}\onslide<3->{\small\textcolor{gray}{(append on sets)}\\ +%\small\hspace{5cm}\textcolor{gray}{$\{ s_1 @ s_2 \;|\; s_1\in L(r) \wedge s_2 \in L(r)^n \}$}} +%} \end{textblock} \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{The Power Operation} - -\begin{itemize} -\item The \alert{\textbf{\boldmath$n$th Power}} of a language: - -\begin{center} -\begin{tabular}{lcl} -\bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ -\bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$} -\end{tabular} -\end{center}\bigskip - -\item[] For example - -\begin{center} -\begin{tabular}{lcl@{\hspace{10mm}}l} -\bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\ -\bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\ -\bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\ -\end{tabular} -\end{center} - -\end{itemize} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{The Star Operation} @@ -1311,70 +1194,236 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{The Meaning of a Regex} + +\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$}\\ + \end{tabular} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{The Meaning of Matching} + +\begin{bubble}[10cm] +\large\bf +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 next lecture is +to decide this problem as fast as possible (unlike Python, +Ruby, Java) + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{Questions} + + \begin{itemize} + \item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip + + \item[] + How many strings are in \bl{$A^4$}\,? + \bigskip\medskip\pause + + + \item[] + What if \bl{$A = \{[a],[b],[c],[]\}$};\\ + how many strings are then in \bl{$A^4$}\,? + \end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] +% \frametitle{Languages (Sets of Strings)} + +% \begin{itemize} + +% \item A \alert{\bf Language} is a set of strings, for example\medskip +% \begin{center} +% \bl{$\{[], hello, foobar, a, abc\}$} +% \end{center}\bigskip + +% \item \alert{\bf Concatenation} for strings and languages + +% \begin{center} +% \begin{tabular}{rcl} +% \bl{$foo\;@\;bar$} & \bl{$=$} & \bl{$foobar$}\medskip\\ +% \bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$} +% \end{tabular} +% \end{center} +% \bigskip + +% \small +% \item [] For example \bl{$A = \{foo, bar\}$}, \bl{$B = \{a, b\}$} + +% \[ +% \bl{A \,@\, B = \{fooa, foob, bara, barb\}} +% \] + + + + +% \end{itemize} +% \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] +% \frametitle{Two Corner Cases} + +% \Large +% \begin{center} +% \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\ +% \bl{$A \,@\, \{\} = \;?$} +% \end{center} + +% \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] +% \frametitle{The Meaning of a Regex} + +% ...all the strings a regular expression can match. + +% \begin{center} +% \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$} & \\ +% \end{tabular} +% \end{center} + +% \begin{textblock}{14}(1.5,13.5)\small +% \bl{$L$} is a function from regular expressions to +% sets of strings (languages):\smallskip\\ +% \bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$} +% \end{textblock} + +% \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] +% \frametitle{The Power Operation} + +% \begin{itemize} +% \item The \alert{\textbf{\boldmath$n$th Power}} of a language: + +% \begin{center} +% \begin{tabular}{lcl} +% \bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ +% \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$} +% \end{tabular} +% \end{center}\bigskip + +% \item[] For example + +% \begin{center} +% \begin{tabular}{lcl@{\hspace{10mm}}l} +% \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\ +% \bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\ +% \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\ +% \end{tabular} +% \end{center} + +% \end{itemize} + +% \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Written Exam} +% \begin{frame}[c] +% \frametitle{Written Exam} -\begin{itemize} -\item Accounts for 80\%.\bigskip +% \begin{itemize} +% \item Accounts for 80\%.\bigskip -\item The question ``\textit{Is this relevant for - the exam?}'' is very demotivating for the lecturer!\bigskip\\ +% \item The question ``\textit{Is this relevant for +% the exam?}'' is very demotivating for the lecturer!\bigskip\\ -\item Deal: Whatever is in the homework (and is not marked - ``\textit{optional}'') is relevant for the exam.\bigskip +% \item Deal: Whatever is in the homework (and is not marked +% ``\textit{optional}'') is relevant for the exam.\bigskip -\item Each lecture has also a handout. There are also handouts about -notation and Scala. -\end{itemize} +% \item Each lecture has also a handout. There are also handouts about +% notation and Scala. +% \end{itemize} -\end{frame} +% \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{Coursework} +% \begin{frame}[t] +% \frametitle{Coursework} -\begin{itemize} -\item Accounts for 20\%. Two strands. Choose \alert{\bf one}!\bigskip -\end{itemize} +% \begin{itemize} +% \item Accounts for 20\%. Two strands. Choose \alert{\bf one}!\bigskip +% \end{itemize} -\begin{columns}[t] -\begin{column}{.5\textwidth} -\underline{\bf Strand 1}\medskip -\begin{itemize} -\item 4 programming tasks: -\begin{itemize} -\item matcher (4\%, 11.10.) -\item lexer (5\%, 04.11.) -\item parser (5\%, 22.11.) -\item compiler (6\%, 13.12.) -\end{itemize} -\item in any lang.~you like,\\ but I want to see the\\ code -\end{itemize} -\end{column} +% \begin{columns}[t] +% \begin{column}{.5\textwidth} +% \underline{\bf Strand 1}\medskip +% \begin{itemize} +% \item 4 programming tasks: +% \begin{itemize} +% \item matcher (4\%, 11.10.) +% \item lexer (5\%, 04.11.) +% \item parser (5\%, 22.11.) +% \item compiler (6\%, 13.12.) +% \end{itemize} +% \item in any lang.~you like,\\ but I want to see the\\ code +% \end{itemize} +% \end{column} -\hspace{-45pt}\vrule{}\hspace{10pt} -\begin{column}{.5\textwidth} -\underline{\bf Strand 2}\smallskip\begin{itemize} -\item one task: prove the correctness of a regular expression matcher in -the \underline{Isabelle} theorem prover -\item 20\%, submission on~13.12.\hspace{-5mm}\mbox{} -\end{itemize} -\end{column} -\end{columns}\medskip +% \hspace{-45pt}\vrule{}\hspace{10pt} +% \begin{column}{.5\textwidth} +% \underline{\bf Strand 2}\smallskip\begin{itemize} +% \item one task: prove the correctness of a regular expression matcher in +% the \underline{Isabelle} theorem prover +% \item 20\%, submission on~13.12.\hspace{-5mm}\mbox{} +% \end{itemize} +% \end{column} +% \end{columns}\medskip -\small -\begin{itemize} -\item Solving more than one strand will {\bf not} give you more -marks. +% \small +% \begin{itemize} +% \item Solving more than one strand will {\bf not} give you more +% marks. -\end{itemize} +% \end{itemize} -\end{frame} +% \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%