
diff -r 04264d0c43bb -r 09efdf5cf07c slides/slides03.tex
--- a/slides/slides03.tex	Mon Oct 07 09:45:11 2013 +0100
+++ b/slides/slides03.tex	Mon Oct 07 16:59:36 2013 +0100
@@ -1,6 +1,6 @@
 \documentclass[dvipsnames,14pt,t]{beamer}
-\usepackage{beamerthemeplainculight}
-\usepackage[T1]{fontenc}
+\usepackage{beamerthemeplaincu}
+%%\usepackage[T1]{fontenc}
 \usepackage[latin1]{inputenc}
 \usepackage{mathpartir}
 \usepackage[absolute,overlay]{textpos}
@@ -24,9 +24,13 @@
 \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments
 \definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords
 \definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc
+\makeatletter
+\lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}}
+\@empty\z@\@empty
+\makeatother
 
 \lstset{language=Java,
-	basicstyle=\ttfamily,
+	basicstyle=\consolas,
 	keywordstyle=\color{javapurple}\bfseries,
 	stringstyle=\color{javagreen},
 	commentstyle=\color{javagreen},
@@ -47,7 +51,7 @@
     private,protected,requires,return,sealed,%
     super,this,throw,trait,true,try,%
     type,val,var,while,with,yield},
-  otherkeywords={=>,<-,<\%,<:,>:,\#,@},
+  otherkeywords={=>,<-,<\%,<:,>:,\#,@,->},
   sensitive=true,
   morecomment=[l]{//},
   morecomment=[n]{/*}{*/},
@@ -57,7 +61,7 @@
 }
 
 \lstset{language=Scala,
-	basicstyle=\ttfamily,
+	basicstyle=\consolas,
 	keywordstyle=\color{javapurple}\bfseries,
 	stringstyle=\color{javagreen},
 	commentstyle=\color{javagreen},
@@ -70,8 +74,9 @@
 	showspaces=false,
 	showstringspaces=false}
 
+
 % beamer stuff 
-\renewcommand{\slidecaption}{AFL 03, King's College London, 10.~October 2012}
+\renewcommand{\slidecaption}{AFL 03, King's College London, 9.~October 2013}
 \newcommand{\bl}[1]{\textcolor{blue}{#1}}       
 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
 
@@ -97,9 +102,8 @@
   \begin{center}
   \begin{tabular}{ll}
   Email:  & christian.urban at kcl.ac.uk\\
-  Of$\!$fice: & S1.27 (1st floor Strand Building)\\
+  Office: & S1.27 (1st floor Strand Building)\\
   Slides: & KEATS (also home work is there)\\
-               & \alert{\bf (I have put a temporary link in there.)}\\
   \end{tabular}
   \end{center}
 
@@ -110,18 +114,39 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Last Week\end{tabular}}
+\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}
 
-Last week I showed you
+They are often used to recognise:\medskip
 
 \begin{itemize}
-\item one simple-minded regular expression matcher (which however does not work in all cases), and\bigskip
-\item one which works provably in all cases
+\item symbols, digits
+\item identifiers
+\item numbers (non-leading zeros)
+\item keywords
+\item comments
+\end{itemize}\bigskip
+
+
+\mbox{}\hfill\bl{\url{http://www.regexper.com}}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Last Week\end{tabular}}
+
+Last week I showed you a regular expression matcher 
+which works provably in all cases.
 
 \begin{center}
-\bl{matcher r s} \;\;if and only if \;\; \bl{s $\in$ $L$(r)}
-\end{center} 
-\end{itemize}
+\bl{$matcher\,r\,s$} \;\;if and only if \;\; \bl{$s \in L(r)$}
+\end{center}\bigskip\bigskip 
+
+\small
+\textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)}
+
   
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -133,18 +158,20 @@
 
 \begin{center}
 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
-  \bl{der c ($\varnothing$)}            & \bl{$\dn$} & \bl{$\varnothing$} & \\
-  \bl{der c ($\epsilon$)}           & \bl{$\dn$} & \bl{$\varnothing$} & \\
-  \bl{der c (d)}           & \bl{$\dn$} & \bl{if c $=$ d then $\epsilon$ else $\varnothing$} & \\
-  \bl{der c (r$_1$ + r$_2$)} & \bl{$\dn$} & \bl{(der c r$_1$) + (der c r$_2$)} & \\
-  \bl{der c (r$_1$ $\cdot$ r$_2$)} & \bl{$\dn$}  & \bl{if nullable r$_1$}\\
-  & & \bl{then ((der c r$_1$) $\cdot$ r$_2$) + (der c r$_2$)}\\ 
-  & & \bl{else (der c r$_1$) $\cdot$ r$_2$}\\
-  \bl{der c (r$^*$)}          & \bl{$\dn$} & \bl{(der c r) $\cdot$ (r$^*$)}\\
+  \bl{$der\, c\, (\varnothing)$}      & \bl{$\dn$} & \bl{$\varnothing$} & \\
+  \bl{$der\, c\, (\epsilon)$}           & \bl{$\dn$} & \bl{$\varnothing$} & \\
+  \bl{$der\, c\, (d)$}                     & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\
+  \bl{$der\, c\, (r_1 + r_2)$}        & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\
+  \bl{$der\, c\, (r_1 \cdot r_2)$}  & \bl{$\dn$}  & \bl{if $nullable (r_1)$}\\
+  & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ 
+  & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\
+  \bl{$der\, c\, (r^*)$}          & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\smallskip\\\pause
+
+  \bl{$der\!s\, []\, r$}     & \bl{$\dn$} & \bl{$r$} & \\
+  \bl{$der\!s\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\
   \end{tabular}
 \end{center}
 
-``the regular expression after \bl{c} has been recognised'' 
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -153,19 +180,24 @@
 \mode<presentation>{
 \begin{frame}[c]
 
-For this we defined the set \bl{Der c A} as
+
+To see what is going on, define
 
 \begin{center}
-\bl{Der c A $\dn$ $\{$ s $|$  c::s $\in$ A$\}$ } 
-\end{center}
+\bl{$Der\,c\,A \dn \{ s \;|\;  c\!::\!s \in A\}$ } 
+\end{center}\bigskip\bigskip
 
-which is called the semantic derivative of a set
-and proved 
+\small
+For \bl{$A = \{"f\!oo", "bar", "f\!rak"\}$} then
 
 \begin{center}
-\bl{$L$(der c r) $=$ Der c ($L$(r))}
+\bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l}
+$Der\,f\,A$ & $=$ & $\{"oo", "rak"\}$\\
+$Der\,b\,A$ & $=$ &  $\{"ar"\}$\\  
+$Der\,a\,A$ & $=$ & $\varnothing$\\
+\end{tabular}}
 \end{center}
-
+ 
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -176,14 +208,14 @@
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}The Idea of the Algorithm\end{tabular}}
 
-If we want to recognise the string \bl{abc} with regular expression \bl{r}
+If we want to recognise the string \bl{$"abc"$} with regular expression \bl{$r$}
 then\medskip
 
 \begin{enumerate}
-\item \bl{Der a ($L$(r))}\pause
-\item \bl{Der b (Der a ($L$(r)))}
-\item \bl{Der c (Der b (Der a ($L$(r))))}\pause
-\item finally we test whether the empty string is in set\pause\medskip
+\item \bl{$Der\,a\,(L(r))$}\pause
+\item \bl{$Der\,b\,(Der\,a\,(L(r)))$}\pause
+\item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r))))$}\pause
+\item finally we test whether the empty string is in this set\pause\medskip
 \end{enumerate}
 
 The matching algorithm works similarly, just over regular expression than sets.
@@ -195,12 +227,12 @@
 \mode<presentation>{
 \begin{frame}[c]
 
-Input: string \bl{abc} and regular expression \bl{r} 
+Input: string \bl{$"abc"$} and regular expression \bl{$r$} 
 
 \begin{enumerate}
-\item \bl{der a r}
-\item \bl{der b (der a r)}
-\item \bl{der c (der b (der a r))}\pause
+\item \bl{$der\,a\,r$}
+\item \bl{$der\,b\,(der\,a\,r)$}
+\item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause
 \item finally check whether the latter regular expression can match the empty string
 \end{enumerate}
 
@@ -211,10 +243,25 @@
 \mode<presentation>{
 \begin{frame}[c]
 
+We proved already
+
+\begin{center}
+\bl{$nullable(r)$} \;if and only if\;  \bl{$"" \in L(r)$}
+\end{center}
+
+by induction on the regular expression.
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
 We need to prove
 
 \begin{center}
-\bl{$L$(der c r) $=$ Der c ($L$(r))}
+\bl{$L(der\,c\,r) = Der\,c\,(L(r))$}
 \end{center}
 
 by induction on the regular expression.
@@ -226,16 +273,16 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Proofs about Rexp\end{tabular}}
+\frametitle{\begin{tabular}{c}Proofs about Rexps\end{tabular}}
 
 \begin{itemize}
 \item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip
-\item \bl{$P$} holds for \bl{r$_1$ + r$_2$} under the assumption that \bl{$P$} already
-holds for \bl{r$_1$} and \bl{r$_2$}.\bigskip
-\item \bl{$P$} holds for \bl{r$_1$ $\cdot$ r$_2$} under the assumption that \bl{$P$} already
-holds for \bl{r$_1$} and \bl{r$_2$}.
-\item \bl{$P$} holds for \bl{r$^*$} under the assumption that \bl{$P$} already
-holds for \bl{r}.
+\item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already
+holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip
+\item \bl{$P$} holds for \bl{$r_1 \cdot r_2$} under the assumption that \bl{$P$} already
+holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip
+\item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already
+holds for \bl{$r$}.
 \end{itemize}
 
 \end{frame}}
@@ -244,7 +291,7 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Proofs about Natural Numbers\\ and Strings\end{tabular}}
+\frametitle{\begin{tabular}{c}Proofs about Natural\\[-1mm] Numbers and Strings\end{tabular}}
 
 \begin{itemize}
 \item \bl{$P$} holds for \bl{$0$} and
@@ -253,7 +300,7 @@
 \end{itemize}\bigskip
 
 \begin{itemize}
-\item \bl{$P$} holds for \bl{\texttt{""}} and
+\item \bl{$P$} holds for \bl{$""$} and
 \item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already
 holds for \bl{$s$}
 \end{itemize}
@@ -261,26 +308,6 @@
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}
-
-\begin{center}
-  \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
-  \bl{r} & \bl{$::=$}  & \bl{$\varnothing$}  & null\\
-         & \bl{$\mid$} & \bl{$\epsilon$}        & empty string / "" / []\\
-         & \bl{$\mid$} & \bl{c}                         & character\\
-         & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$} & sequence\\
-         & \bl{$\mid$} & \bl{r$_1$ + r$_2$}  & alternative / choice\\
-         & \bl{$\mid$} & \bl{r$^*$}                   & star (zero or more)\\
-  \end{tabular}\bigskip\pause
-  \end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -290,7 +317,7 @@
 
 A \alert{language} is a set of strings.\bigskip
 
-A \alert{regular expression} specifies a set of strings or language.\bigskip
+A \alert{regular expression} specifies a language.\bigskip
 
 A language is \alert{regular} iff there exists
 a regular expression that recognises all its strings.\bigskip\bigskip\pause
@@ -340,6 +367,19 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
+\frametitle{\begin{tabular}{c}Regular Languages\end{tabular}}
+
+A language (a set of strings) is \alert{regular} iff there exists
+a regular expression that recognises all its strings.\bigskip\bigskip\pause
+
+
+Do you think there are languages that are {\bf not} regular?
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
 \frametitle{\begin{tabular}{c}Regular Exp's for Lexing\end{tabular}}
 
 Lexing separates strings into ``words'' / components.
@@ -375,6 +415,26 @@
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Automata\end{tabular}}
+
+A deterministic finite automaton consists of:
+
+\begin{itemize}
+\item a set of states
+\item one of these states is the start state
+\item some states are accepting states, and
+\item there is transition function\medskip 
+
+\small
+which takes a state as argument and a character and produces a new state\smallskip\\
+this function might not always be defined
+\end{itemize}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
 \end{document}




