\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 01, King's College London, 26.~September 2012}

\begin{document}

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

\mode<presentation>{

\begin{frame}<1>[t]

\frametitle{%

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

  \\[-3mm]

  \LARGE Automata and \\[-2mm] 

  \LARGE Formal Languages (1)\\[-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}[c]

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

\begin{tabular}{c}

\includegraphics[scale=0.15]{pics/servers.png}\\[-2mm]

\small Server

\end{tabular}

\end{textblock}

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

  \begin{tikzpicture}[scale=1.1]

  \draw[white] (0,1) node (X) {};

  \draw[white] (2,1) node (Y) {};

   \draw[white] (0,0) node (X1) {};

  \draw[white] (2,0) node (Y1) {};

   \draw[white] (0,-1) node (X2) {};

  \draw[white] (2,-1) node (Y2) {};

  \draw[red, <-, line width = 2mm] (X) -- (Y);

  \node [inner sep=5pt,label=above:\textcolor{black}{GET request}] at ($ (X)!.5!(Y) $) {};

  \draw[red, ->, line width = 2mm] (X1) -- (Y1);

  \node [inner sep=5pt,label=above:\textcolor{black}{webpage}] at ($ (X1)!.5!(Y1) $) {};

  \draw[red, <-, line width = 2mm] (X2) -- (Y2);

  \node [inner sep=7pt,label=above:\textcolor{black}{POST data}] at ($ (X2)!.5!(Y2) $) {};

  \end{tikzpicture}

\end{textblock}

\begin{textblock}{1}(9,5.5)

\begin{tabular}{c}

\includegraphics[scale=0.15]{pics/laptop.png}\\[-2mm]

\small Browser

\end{tabular}

\end{textblock}

\only<2>{  

\begin{textblock}{10}(2,13.5)

\begin{itemize}

\item programming languages, compilers

\end{itemize}

\end{textblock}}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

transforming strings into structured data\\[10mm]

{\LARGE\bf Lexing}\medskip\\

\hspace{5mm}(recognising ``words'')\\[6mm]

{\LARGE\bf Parsing}\medskip\\

\hspace{5mm}(recognising ``sentences'')

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

The subject is quite old:

\begin{itemize}

\item Turing Machines, 1936

\item first compiler for COBOL, 1957 (Grace Hopper)

\item but surprisingly research papers are still published now

\end{itemize}

\begin{flushright}

\includegraphics[scale=0.3]{pics/hopper.jpg}\\

\footnotesize\textcolor{gray}{Grace Hopper}

\end{flushright}

{\footnotesize\textcolor{gray}{(she made it to David Letterman's Tonight Show, \url{http://www.youtube.com/watch?v=aZOxtURhfEU})}}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}This Course\end{tabular}}

\begin{itemize}

\item regular expression / regular expression matching

\item a bit of sets (of strings)

\item automata

\item the Myhill-Nerode theorem

\item parsing

\item grammars

\item a small interpreter / webbrowser

\end{itemize}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}This Course\end{tabular}}

\begin{itemize}

\item the ultimate goal is to implement a small web-browser (really small)\bigskip

\end{itemize}

Let's start with:

\begin{itemize}

\item a web-crawler

\item an email harvester

\item a web-scraper

\end{itemize}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Scala\end{tabular}}

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

\texttt{\lstinputlisting{app0.scala}}}\pause\bigskip

\footnotesize

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

\texttt{\lstinputlisting{app1.scala}}}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Cookies\end{tabular}}

\begin{textblock}{1}(1.5,5)

\begin{tabular}{c}

%\includegraphics[scale=0.15]{pics/servers.png}\\[-2mm]

\small Servers from\\[-2mm] 

\small Dot.com Inc.

\end{tabular}

\end{textblock}

\begin{textblock}{1}(5.6,5.6)

  \begin{tikzpicture}[scale=2.5]

  \draw[white] (0,0) node (X) {};

  \draw[white] (1,0) node (Y) {};

  \draw[white] (0.05,-0.3) node (X1) {};

  \draw[white] (0.95,-0.3) node (Y1) {};

  \only<1-2>{\draw[red, <-, line width = 2mm] (X) -- (Y);

  \node [inner sep=5pt,label=above:\textcolor{black}{GET request}] at ($ (X)!.5!(Y) $) {};}

  \only<1>{\draw[white, <-, line width = 1mm] (X1) -- (Y1);

  \node [inner sep=2pt,label=below:\textcolor{white}{read a cookie}] at ($ (X1)!.5!(Y1) $) {};}

  \only<2>{\draw[red, <-, line width = 1mm] (X1) -- (Y1);

  \node [inner sep=2pt,label=below:\textcolor{black}{read a cookie}] at ($ (X1)!.5!(Y1) $) {};}

  \only<3->{\draw[red, ->, line width = 2mm] (X) -- (Y);

  \node [inner sep=5pt,label=above:\textcolor{black}{webpage}] at ($ (X)!.5!(Y) $) {};}

  \only<3->{\draw[red, ->, line width = 1mm] (X1) -- (Y1);

  \node [inner sep=2pt,label=below:\textcolor{black}{write a cookie}] at ($ (X1)!.5!(Y1) $) {};}

  \end{tikzpicture}

\end{textblock}

\begin{textblock}{1}(9.5,5.5)

\begin{tabular}{c}

%\includegraphics[scale=0.15]{pics/laptop.png}\\[-2mm]

\small Client

\end{tabular}

\end{textblock}

\only<4->{  

\begin{textblock}{13}(1,11)  

\small\begin{itemize}

\item cookies: max 4KB data\\[-2mm]

\item cookie theft, cross-site scripting attacks\\[-2mm]

\item session cookies, persistent cookies, HttpOnly cookies, third-party cookies, zombie cookies 

\end{itemize}  

\end{textblock}}

\only<5>{

\begin{textblock}{11}(1,3)

\begin{tikzpicture}

\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 

{\normalsize\color{darkgray}

\begin{minipage}{10cm}\raggedright\small

{\bf EU Privacy Directive about Cookies:}\smallskip\\

``In May 2011, a European Union law was passed stating that websites that leave non-essential cookies on visitors' devices have to alert the visitor and get acceptance from them. This law applies to both individuals and businesses based in the EU regardless of the nationality of their website's visitors or the location of their web host. It is not enough to simply update a website's terms and conditions or privacy policy. The deadline to comply with the new EU cookie law was 26th May 2012 and failure to do so could mean a fine of up to \pounds{}500,000.''

\hfill\small\textcolor{gray}{$\rightarrow$BBC News}

\end{minipage}};

\end{tikzpicture}

\end{textblock}}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[t]

\begin{itemize}

\item While cookies are per web-page, this can be easily circumvented.

\end{itemize}

\begin{textblock}{1}(1.5,4.5)

\begin{tabular}{c}

%\includegraphics[scale=0.07]{pics/servers.png}\\[-2mm]

\small Pet Store\\[-2mm] 

\small Dot.com\\[-2mm] 

\end{tabular}

\end{textblock}

\begin{textblock}{1}(1.5,8)

\begin{tabular}{c}

%\includegraphics[scale=0.07]{pics/servers.png}\\[-2mm]

\small Dating.com

\end{tabular}

\end{textblock}  

\begin{textblock}{1}(10.5,7.5)

\begin{tabular}{c}

%\includegraphics[scale=0.07]{pics/servers.png}\\[-2mm]

\small Evil-Ad-No\\[-2mm]

\small Privacy.com

\end{tabular}

\end{textblock}  

\begin{textblock}{1}(6,10.5)

\begin{tabular}{c}

%\includegraphics[scale=0.16]{pics/rman.png}\\[-1mm]

\small you

\end{tabular}

\end{textblock}  

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

  \begin{tikzpicture}[scale=1]

  \draw[white] (0,0.5) node (X) {};

  \draw[white] (5.7,-1) node (Y) {};

  \draw[red, ->, line width = 0.5mm] (X) -- (Y);

  \node [inner sep=5pt,label=above:\textcolor{black}{}] at ($ (X)!.5!(Y) $) {};

  \end{tikzpicture}

\end{textblock}

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

  \begin{tikzpicture}[scale=1]

  \draw[white] (0,0) node (X) {};

  \draw[white] (5.7,0) node (Y) {};

  \draw[red, ->, line width = 0.5mm] (X) -- (Y);

  \node [inner sep=5pt,label=above:\textcolor{black}{}] at ($ (X)!.5!(Y) $) {};

  \end{tikzpicture}

\end{textblock}

\begin{textblock}{1}(3.3,9.3)

  \begin{tikzpicture}[scale=1.2]

  \draw[white] (0,0) node (X) {};

  \draw[white] (1.5,-1) node (Y) {};

  \draw[red, <->, line width = 2mm] (X) -- (Y);

  \node [inner sep=5pt,label=above:\textcolor{black}{}] at ($ (X)!.5!(Y) $) {};

  \draw[white] (0.9,0.3) node (X1) {};

  \draw[white] (1.9,-1) node (Y1) {};

  \draw[red, <->, line width = 2mm] (X1) -- (Y1);

  \node [inner sep=5pt,label=above:\textcolor{black}{}] at ($ (X1)!.5!(Y1) $) {};

  \end{tikzpicture}

\end{textblock}  

\begin{textblock}{1}(8.6,10.1)

  \begin{tikzpicture}[scale=0.9]

  \draw[white] (0,0) node (X) {};

  \draw[white] (-2,-1) node (Y) {};

  \draw[red, <->, line width = 0.5mm] (X) -- (Y);

  \node [inner sep=5pt,label=above:\textcolor{black}{}] at ($ (X)!.5!(Y) $) {};

  \end{tikzpicture}

\end{textblock}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}My First Webapp\end{tabular}}

{\bf GET request:}\smallskip

\begin{enumerate}

\item read the cookie from client

\item if none is present, set \texttt{visits} to \textcolor{blue}{$0$}

\item if cookie is present, extract \texttt{visits} counter

\item if \texttt{visits} is greater or equal \textcolor{blue}{$10$}, \\

print a valued customer message\\

otherwise just a normal message

\item increase \texttt{visits} by \textcolor{blue}{$1$} and store new cookie with client

\end{enumerate}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\mbox{}\\[-9mm]

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

%\texttt{\lstinputlisting{app2.scala}}}

\footnotesize

\begin{itemize}

\item cookie value encoded as hash

\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 exams?'' 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}}

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