# HG changeset patch # User Christian Urban # Date 1349224868 -3600 # Node ID 32d56fef14a7a45a01de7f7feed999b6255a0ac9 # Parent f5a6270adebc2a84f18ce7eabf65b2cff5cf4db5 tuned diff -r f5a6270adebc -r 32d56fef14a7 slides02.pdf Binary file slides02.pdf has changed diff -r f5a6270adebc -r 32d56fef14a7 slides02.tex --- a/slides02.tex Sun Sep 30 00:21:40 2012 +0100 +++ b/slides02.tex Wed Oct 03 01:41:08 2012 +0100 @@ -84,21 +84,21 @@ \begin{tabular}{@ {}c@ {}} \\[-3mm] \LARGE Automata and \\[-2mm] - \LARGE Formal Languages (2)\\[-3mm] + \LARGE Formal Languages (2)\\[3mm] \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?)} - \end{center} + %\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?)} + %\end{center} \normalsize \begin{center} \begin{tabular}{ll} Email: & christian.urban at kcl.ac.uk\\ Of$\!$fice: & S1.27 (1st floor Strand Building)\\ - Slides: & KEATS + Slides: & KEATS \end{tabular} \end{center} @@ -108,6 +108,18 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Languages\end{tabular}} + +A \alert{language} is a set of strings.\bigskip + +A \alert{regular expression} specifies a set of strings or language. + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ \begin{frame}[t] \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} @@ -130,6 +142,22 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ +\begin{frame}[t] +\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} + +Their implementation in Scala: + +{\lstset{language=Scala}\fontsize{8}{10}\selectfont +\texttt{\lstinputlisting{app51.scala}}} + + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ \begin{frame}[c] \frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}} @@ -147,9 +175,39 @@ \textcolor{gray}{$L$(r)$^{n+1}$ $\;\dn\;$ $L$(r) @ $L$(r)$^n$} \end{textblock} +\only<2->{ +\begin{textblock}{5}(11,5) +\textcolor{gray}{\small +A @ B\\ +\ldots you take out every string from A and +concatenate it with every string in B +} +\end{textblock}} + +\only<3->{ +\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}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] + +\large +\begin{center} +What is \bl{$L$(a$^*$)}? +\end{center} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + \newcommand{\YES}{\textcolor{gray}{yes}} \newcommand{\NO}{\textcolor{gray}{no}} \newcommand{\FORALLR}{\textcolor{gray}{$\forall$ r.}} @@ -159,7 +217,7 @@ \frametitle{\begin{tabular}{c}Reg Exp Equivalences\end{tabular}} \begin{center} -\begin{tabular}{lrcl@ {\hspace{7mm}}l} +\begin{tabular}{l@ {\hspace{7mm}}rcl@ {\hspace{7mm}}l} &\bl{(a + b) + c} & \bl{$\equiv^?$} & \bl{a + (b + c)} & \onslide<2->{\YES}\\ &\bl{a + a} & \bl{$\equiv^?$} & \bl{a} & \onslide<3->{\YES}\\ &\bl{(a $\cdot$ b) $\cdot$ c} & \bl{$\equiv^?$} & \bl{a $\cdot$ (b $\cdot$ c)} & \onslide<4->{\YES}\\ @@ -205,12 +263,17 @@ \item given a regular expression \bl{r} and a string \bl{s}, say yes or no for whether \begin{center} \bl{s $\in$ $L$(r)} -\end{center}\bigskip\bigskip\pause -\only<2>{\item foo}% -\only<3>{\item bar} +\end{center} +or not.\bigskip\bigskip\pause +\end{itemize}\pause + +\small +\begin{itemize} +\item Identifiers (strings of letters or digits, starting with a letter) +\item Integers (a non-empty sequence of digits) +\item Keywords (else, if, while, \ldots) +\item White space (a non-empty sequence of blanks, newlines and tabs) \end{itemize} - - \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -297,66 +360,6 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}This Course\end{tabular}} - -We will have a look at: - -\begin{itemize} -\item regular expressions / regular expression matching -\item automata -\item the Myhill-Nerode theorem -\item parsing -\item grammars -\item a small interpreter / web browser -\end{itemize} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Exam\end{tabular}} - -\begin{itemize} -\item The question ``Is this relevant for the exam?'' is not appreciated!\bigskip\\ - -Whatever is in the homework sheets (and is not marked optional) is relevant for the -exam.\\ No code needs to be written. -\end{itemize} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Maps in Scala\end{tabular}} - -\begin{itemize} -\item {\bf\texttt{map}} takes a function, say f, and applies it to every element of the list: -\end{itemize} - -\begin{textblock}{15}(2,7) -\fontsize{13}{14}\selectfont -\bf\texttt{List(1, 2, 3, 4, 5, 6, 7, 8, 9)} -\end{textblock} - -\begin{textblock}{15}(2,10) -\fontsize{13}{14}\selectfont -\bf\texttt{List(1, 4, 9, 16, 25, 36, 49, 64, 81)} -\end{textblock} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - \end{document}