\documentclass[dvipsnames,14pt,t]{beamer}

\usepackage{beamerthemeplainculight}

\usepackage[T1]{fontenc}

\usepackage[latin1]{inputenc}

\usepackage{mathpartir}

\usepackage[absolute,overlay]{textpos}

\usepackage{ifthen}

\usepackage{tikz}

\usepackage{pgf}

\usepackage{calc} 

\usepackage{ulem}

\usepackage{courier}

\usepackage{listings}

\renewcommand{\uline}[1]{#1}

\usetikzlibrary{arrows}

\usetikzlibrary{automata}

\usetikzlibrary{shapes}

\usetikzlibrary{shadows}

\usetikzlibrary{positioning}

\usetikzlibrary{calc}

\usepackage{graphicx} 

\definecolor{javared}{rgb}{0.6,0,0} % for strings

\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

\lstset{language=Java,

	basicstyle=\ttfamily,

	keywordstyle=\color{javapurple}\bfseries,

	stringstyle=\color{javagreen},

	commentstyle=\color{javagreen},

	morecomment=[s][\color{javadocblue}]{/**}{*/},

	numbers=left,

	numberstyle=\tiny\color{black},

	stepnumber=1,

	numbersep=10pt,

	tabsize=2,

	showspaces=false,

	showstringspaces=false}

\lstdefinelanguage{scala}{

  morekeywords={abstract,case,catch,class,def,%

    do,else,extends,false,final,finally,%

    for,if,implicit,import,match,mixin,%

    new,null,object,override,package,%

    private,protected,requires,return,sealed,%

    super,this,throw,trait,true,try,%

    type,val,var,while,with,yield},

  otherkeywords={=>,<-,<\%,<:,>:,\#,@},

  sensitive=true,

  morecomment=[l]{//},

  morecomment=[n]{/*}{*/},

  morestring=[b]",

  morestring=[b]',

  morestring=[b]"""

}

\lstset{language=Scala,

	basicstyle=\ttfamily,

	keywordstyle=\color{javapurple}\bfseries,

	stringstyle=\color{javagreen},

	commentstyle=\color{javagreen},

	morecomment=[s][\color{javadocblue}]{/**}{*/},

	numbers=left,

	numberstyle=\tiny\color{black},

	stepnumber=1,

	numbersep=10pt,

	tabsize=2,

	showspaces=false,

	showstringspaces=false}

% beamer stuff 

\renewcommand{\slidecaption}{AFL 02, King's College London, 3.~October 2012}

\newcommand{\bl}[1]{\textcolor{blue}{#1}}       

\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}<1>[t]

\frametitle{%

  \begin{tabular}{@ {}c@ {}}

  \\[-3mm]

  \LARGE Automata and \\[-2mm] 

  \end{tabular}}

\normalsize

  \begin{center}

  \begin{tabular}{ll}

  Email:  & christian.urban at kcl.ac.uk\\

  Of$\!$fice: & S1.27 (1st floor Strand Building)\\

  \end{tabular}

  \end{center}

\end{frame}}

 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[t]

\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}

Their inductive definition:

\begin{textblock}{6}(2,5)

  \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{textblock}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}}

\begin{textblock}{15}(1,4)

 \begin{tabular}{@ {}rcl}

 \bl{$L$($\varnothing$)}  & \bl{$\dn$} & \bl{$\varnothing$}\\

 \bl{$L$($\epsilon$)}        & \bl{$\dn$} & \bl{$\{$""$\}$}\\

 \bl{$L$(c)}                         & \bl{$\dn$} & \bl{$\{$"c"$\}$}\\

 \bl{$L$(r$_1$ + r$_2$)} & \bl{$\dn$} & \bl{$L$(r$_1$) $\cup$ $L$(r$_2$)}\\

 \bl{$L$(r$_1$ $\cdot$ r$_2$)}  & \bl{$\dn$} & \bl{$L$(r$_1$) @ $L$(r$_2$)}\\

 \bl{$L$(r$^*$)}                   & \bl{$\dn$} & \bl{$\bigcup_{n \ge 0}$ $L$(r)$^n$}\\

  \end{tabular}\bigskip

\hspace{5mm}\textcolor{gray}{$L$(r)$^0$ $\;\dn\;$ $\{$""$\}$}\\

\textcolor{gray}{$L$(r)$^{n+1}$ $\;\dn\;$ $L$(r) @ $L$(r)$^n$}  

\end{textblock}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

\newcommand{\YES}{\textcolor{gray}{yes}}

\newcommand{\NO}{\textcolor{gray}{no}}

\newcommand{\FORALLR}{\textcolor{gray}{$\forall$ r.}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Reg Exp Equivalences\end{tabular}}

\begin{center}

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

&\bl{a $\cdot$ a} & \bl{$\equiv^?$} & \bl{a} & \onslide<5->{\NO}\\

&\bl{$\epsilon^*$} & \bl{$\equiv^?$} & \bl{$\epsilon$} & \onslide<6->{\YES}\\

&\bl{$\varnothing^*$} & \bl{$\equiv^?$} & \bl{$\varnothing$} & \onslide<7->{\NO}\\

\FORALLR &\bl{r $\cdot$ $\epsilon$} & \bl{$\equiv^?$} & \bl{r} & \onslide<8->{\YES}\\

\FORALLR &\bl{r + $\epsilon$} & \bl{$\equiv^?$} & \bl{r} & \onslide<9->{\NO}\\

\FORALLR &\bl{r + $\varnothing$} & \bl{$\equiv^?$} & \bl{r} & \onslide<10->{\YES}\\

\FORALLR &\bl{r $\cdot$ $\varnothing$} & \bl{$\equiv^?$} & \bl{r} & \onslide<11->{\NO}\\

&\bl{c $\cdot$ (a + b)} & \bl{$\equiv^?$} & \bl{(c $\cdot$ a) + (c $\cdot$ b)} & \onslide<12->{\YES}\\

&\bl{a$^*$} & \bl{$\equiv^?$} & \bl{$\epsilon$ + (a $\cdot$ a$^*$)} & \onslide<13->{\YES}

\end{tabular}

\end{center}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}The Meaning of Matching\end{tabular}}

\large

a regular expression \bl{r} matches a string \bl{s} is defined as

\begin{center}

\bl{s $\in$ $L$(r)}\\ 

\end{center}\bigskip\bigskip\pause

\small

if \bl{r$_1$ $\equiv$ r$_2$}, then \bl{$s$ $\in$ $L$(r$_1$)} iff \bl{$s$ $\in$ $L$(r$_2$)}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[t]

\frametitle{\begin{tabular}{c}A Matching Algorithm\end{tabular}}

\begin{itemize}

\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{itemize}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}A Matching Algorithm\end{tabular}}

\small

whether a regular expression matches the empty string:\medskip

{\lstset{language=Scala}\fontsize{8}{10}\selectfont

\texttt{\lstinputlisting{app5.scala}}}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}}

\large

If \bl{r} matches the string \bl{c::s}, what is a regular expression that matches \bl{s}?\bigskip\bigskip\bigskip\bigskip

\small

\bl{der c r} gives the answer

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}The Derivative\end{tabular}}

\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 [] 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{((der c r$_1$) $\cdot$ r$_2$) + } & \\

       &          & \bl{\hspace{3mm}(if nullable r$_1$ then der c r$_2$ else $\varnothing$)}\\

  \bl{der c (r$^*$)}          & \bl{$\dn$} & \bl{(der c r) $\cdot$ (r$^*$)} &\smallskip\\\pause

  \bl{ders [] r}     & \bl{$\dn$} & \bl{r} & \\

  \bl{ders (c::s) r} & \bl{$\dn$} & \bl{ders s (der c r)} & \\

  \end{tabular}

\end{center}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}The Derivative\end{tabular}}

{\lstset{language=Scala}\fontsize{8}{10}\selectfont

\texttt{\lstinputlisting{app6.scala}}}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}The Rexp Matcher\end{tabular}}

{\lstset{language=Scala}\fontsize{8}{10}\selectfont

\texttt{\lstinputlisting{app7.scala}}}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

\end{document}

%%% Local Variables:  

%%% mode: latex

%%% TeX-master: t

%%% End: