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