--- 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.