\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] 
  \LARGE Formal Languages (2)\\[-3mm] 
  \end{tabular}}

  \begin{center}
  \includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm}
  \includegraphics[scale=0.31]{pics/ante2.jpg}\\
  \footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)}
  \end{center}

\normalsize
  \begin{center}
  \begin{tabular}{ll}
  Email:  & christian.urban at kcl.ac.uk\\
  Of$\!$fice: & S1.27 (1st floor Strand Building)\\
  Slides: & KEATS
  \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}
\begin{tabular}{lrcl@ {\hspace{7mm}}l}
&\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{center}\bigskip\bigskip\pause
\only<2>{\item foo}%
\only<3>{\item bar}
\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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}This Course\end{tabular}}

We will have a look at:

\begin{itemize}
\item regular expressions / regular expression matching
\item automata
\item the Myhill-Nerode theorem
\item parsing
\item grammars
\item a small interpreter / web browser
\end{itemize}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Exam\end{tabular}}

\begin{itemize}
\item The question ``Is this relevant for the exam?'' is not appreciated!\bigskip\\

Whatever is in the homework sheets (and is not marked optional) is relevant for the
exam.\\ No code needs to be written.
\end{itemize}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{\begin{tabular}{c}Maps in Scala\end{tabular}}

\begin{itemize}
\item {\bf\texttt{map}} takes a function, say f, and applies it to every element of the list:
\end{itemize}

\begin{textblock}{15}(2,7)
\fontsize{13}{14}\selectfont
\bf\texttt{List(1, 2, 3, 4, 5, 6, 7, 8, 9)}
\end{textblock}

\begin{textblock}{15}(2,10)
\fontsize{13}{14}\selectfont
\bf\texttt{List(1, 4, 9, 16, 25, 36, 49, 64, 81)}
\end{textblock}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   


\end{document}

%%% Local Variables:  
%%% mode: latex
%%% TeX-master: t
%%% End: