# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1381264633 -3600
# Node ID e3a8cf96f570ed4a69d266d8a6b55b1923209ab7
# Parent  09efdf5cf07c9d22e3cc700ea2a90fe948dec90b
added

diff -r 09efdf5cf07c -r e3a8cf96f570 slides/slides03.pdf
Binary file slides/slides03.pdf has changed
diff -r 09efdf5cf07c -r e3a8cf96f570 slides/slides03.tex
--- a/slides/slides03.tex	Mon Oct 07 16:59:36 2013 +0100
+++ b/slides/slides03.tex	Tue Oct 08 21:37:13 2013 +0100
@@ -100,10 +100,10 @@
 
 \normalsize
   \begin{center}
-  \begin{tabular}{ll}
+  \begin{tabular}{lp{8cm}}
   Email:  & christian.urban at kcl.ac.uk\\
   Office: & S1.27 (1st floor Strand Building)\\
-  Slides: & KEATS (also home work is there)\\
+  Slides: & KEATS (also home work and coursework is there)\\
   \end{tabular}
   \end{center}
 
@@ -116,7 +116,7 @@
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}
 
-They are often used to recognise:\medskip
+In programming languages they are often used to recognise:\medskip
 
 \begin{itemize}
 \item symbols, digits
@@ -138,7 +138,7 @@
 \frametitle{\begin{tabular}{c}Last Week\end{tabular}}
 
 Last week I showed you a regular expression matcher 
-which works provably in all cases.
+which works provably correctly in all cases.
 
 \begin{center}
 \bl{$matcher\,r\,s$} \;\;if and only if \;\; \bl{$s \in L(r)$}
@@ -218,7 +218,7 @@
 \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.
+The matching algorithm works similarly, just over regular expression instead of sets.
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
@@ -233,7 +233,7 @@
 \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
+\item finally check whether the last regular expression can match the empty string
 \end{enumerate}
 
 \end{frame}}
@@ -249,7 +249,12 @@
 \bl{$nullable(r)$} \;if and only if\;  \bl{$"" \in L(r)$}
 \end{center}
 
-by induction on the regular expression.
+by induction on the regular expression.\bigskip\pause
+
+\begin{center}
+\huge\bf \alert{Any Questions?}
+\end{center}
+
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -265,7 +270,6 @@
 \end{center}
 
 by induction on the regular expression.
-
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
@@ -322,7 +326,7 @@
 A language is \alert{regular} iff there exists
 a regular expression that recognises all its strings.\bigskip\bigskip\pause
 
-\textcolor{gray}{not all languages are regular, e.g.~\bl{a$^n$b$^n$}.}
+\textcolor{gray}{not all languages are regular, e.g.~\bl{$a^nb^n$}.}
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
@@ -332,17 +336,18 @@
 \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
+   \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}
   \end{center}
-
-How about ranges \bl{[a-z]}, \bl{r$^\text{+}$} and \bl{!r}?
+  
+How about ranges \bl{$[a\mbox{-}z]$}, \bl{$r^+$} and \bl{$\sim{}r$}? Do they increase the
+set of languages we can recognise?
   
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -353,11 +358,18 @@
 \frametitle{\begin{tabular}{c}Negation of Regular Expr's\end{tabular}}
 
 \begin{itemize}
-\item \bl{!r}  \hspace{6mm} (everything that \bl{r} cannot recognise)\medskip
-\item \bl{$L$(!r) $\dn$ UNIV - $L$(r)}\medskip
-\item \bl{nullable (!r) $\dn$ not (nullable(r))}\medskip
-\item \bl{der\,c\,(!r) $\dn$ !(der\,c\,r)}
-\end{itemize}
+\item \bl{$\sim{}r$}  \hspace{6mm} (everything that \bl{r} cannot recognise)\medskip
+\item \bl{$L(\sim{}r) \dn UNIV - L(r)$}\medskip
+\item \bl{$nullable (r) \dn not (nullable(r))$}\medskip
+\item \bl{$der\,c\,(\sim{}r) \dn \;\sim{}(der\,c\,r)$}
+\end{itemize}\bigskip\pause
+
+Used often for comments:
+
+\[
+\bl{/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /}
+\]
+
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -367,19 +379,6 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \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.