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

\usepackage{../slides}

\usepackage{../graphics}

\usepackage{../langs}

\usepackage{../data}

\hfuzz=220pt 

\pgfplotsset{compat=1.11}

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

% beamer stuff 

\renewcommand{\slidecaption}{AFL 05, King's College London}

\begin{document}

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

\begin{frame}[t]

\frametitle{%

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

  \\[-3mm]

  \LARGE Automata and \\[-2mm] 

  \LARGE Formal Languages (5)\\[3mm] 

  \end{tabular}}

  \normalsize

  \begin{center}

  \begin{tabular}{ll}

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

  Office: & S1.27 (1st floor Strand Building)\\

  Slides: & KEATS (also home work is there)\\

  \end{tabular}

  \end{center}

\end{frame}

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

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

\begin{frame}[c]

Regular expressions and their corresponding values:

\begin{center}

\begin{columns}

\begin{column}{3cm}

\begin{tabular}{@{}rrl@{}}

  \bl{$r$} & \bl{$::=$}  & \bl{$\varnothing$}\\

           & \bl{$\mid$} & \bl{$\epsilon$}   \\

           & \bl{$\mid$} & \bl{$c$}          \\

           & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\

           & \bl{$\mid$} & \bl{$r_1 + r_2$}   \\

  \\

           & \bl{$\mid$} & \bl{$r^*$}         \\

  \end{tabular}

\end{column}

\begin{column}{3cm}

\begin{tabular}{@{\hspace{-7mm}}rrl@{}}

  \bl{$v$} & \bl{$::=$}  & \\

           &             & \bl{$Empty$}   \\

           & \bl{$\mid$} & \bl{$Char(c)$}          \\

           & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\

           & \bl{$\mid$} & \bl{$Left(v)$}   \\

           & \bl{$\mid$} & \bl{$Right(v)$}  \\

           & \bl{$\mid$} & \bl{$[v_1,\ldots\,v_n]$} \\

  \end{tabular}

\end{column}

\end{columns}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\begin{textblock}{10}(3,5)

\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]

\node (r1)  {\bl{$r_1$}};

\node (r2) [right=of r1] {\bl{$r_2$}};

\draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};

\node (r3) [right=of r2] {\bl{$r_3$}};

\draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};

\node (r4) [right=of r3] {\bl{$r_4$}};

\draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};

\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};

\node (v4) [below=of r4] {\bl{$v_4$}};

\draw[->,line width=1mm]  (r4) -- (v4);

\node (v3) [left=of v4] {\bl{$v_3$}};

\draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};

\node (v2) [left=of v3] {\bl{$v_2$}};

\draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};

\node (v1) [left=of v2] {\bl{$v_1$}};

\draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};

\draw[->,line width=0.5mm]  (r3) -- (v3);

\draw[->,line width=0.5mm]  (r2) -- (v2);

\draw[->,line width=0.5mm]  (r1) -- (v1);

\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};

\end{tikzpicture}

\end{textblock}

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

\begin{bubble}[6cm]

\small

\begin{tabular}{ll}

\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\

\bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\

\bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\

\bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\

\end{tabular}

\end{bubble}

\end{textblock}

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

\begin{bubble}[7.6cm]

\small

\begin{tabular}{ll}

\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\

\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\

\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\

\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\

\end{tabular}

\end{bubble}

\end{textblock}

\begin{textblock}{6}(12,11.4)

\begin{bubble}[2cm]

\small

\begin{tabular}{ll}

\bl{$|v_1|$}: & \bl{$abc$}\\

\bl{$|v_2|$}: & \bl{$bc$}\\

\bl{$|v_3|$}: & \bl{$c$}\\

\bl{$|v_4|$}: & \bl{$[]$}

\end{tabular}

\end{bubble}

\end{textblock}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Simplification}

\begin{itemize}

\item If we simplify after the derivative, then we are builing the

value for the simplified regular expression, but \emph{not} for the original

regular expression.

\end{itemize}

\begin{center}

\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]

\node (r1)  {\bl{$r_1$}};

\node (r2) [right=of r1] {\bl{$r_2$}};

\draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};

\node (r3) [right=of r2] {\bl{$r_3$}};

\draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};

\node (r4) [right=of r3] {\bl{$r_4$}};

\draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};

\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};

\node (v4) [below=of r4] {\bl{$v_4$}};

\draw[->,line width=1mm]  (r4) -- (v4);

\node (v3) [left=of v4] {\bl{$v_3$}};

\draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};

\node (v2) [left=of v3] {\bl{$v_2$}};

\draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};

\node (v1) [left=of v2] {\bl{$v_1$}};

\draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};

\draw[->,line width=0.5mm]  (r3) -- (v3);

\draw[->,line width=0.5mm]  (r2) -- (v2);

\draw[->,line width=0.5mm]  (r1) -- (v1);

\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};

\end{tikzpicture}

\end{center}

\small

\hspace{4.5cm}\bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}

$\mapsto$

\bl{$\epsilon$}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Records}

\begin{itemize}

\item \bl{$nullable(x:r) \dn nullable(r)$}

\item \bl{$der\,c\,(x:r) \dn (x:der\,c\,r)$}

\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$}

\item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$}

\small

for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{While Tokens}

\begin{center}

\begin{tabular}{@{}r@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}

\pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\ 

                  &       & \phantom{(}\pcode{("i" : ID)} +\\ 

                  &       & \phantom{(}\pcode{("o" : OP)} + \\

                  &       & \phantom{(}\pcode{("n" : NUM)} + \\

                  &       & \phantom{(}\pcode{("s" : SEMI)} +\\ 

                  &       & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\ 

                  &       & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\ 

                  &       & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$}

\end{tabular}

\end{center}

\end{frame}

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

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

\begin{frame}[t]

\consolas

\begin{center}

\end{center}

\only<1>{

\small\begin{tabular}{l}

KEYWORD(if),\\ 

WHITESPACE,\\ 

IDENT(true),\\ 

WHITESPACE,\\ 

KEYWORD(then),\\ 

WHITESPACE,\\ 

KEYWORD(then),\\ 

WHITESPACE,\\ 

NUM(42),\\ 

WHITESPACE,\\ 

KEYWORD(else),\\ 

WHITESPACE,\\ 

OP(+)

\end{tabular}}

\only<2>{

\small\begin{tabular}{l}

KEYWORD(if),\\ 

IDENT(true),\\ 

KEYWORD(then),\\ 

KEYWORD(then),\\ 

NUM(42),\\ 

KEYWORD(else),\\ 

OP(+)

\end{tabular}}

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

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

\begin{frame}[c]

\begin{itemize}

\item Longest match rule (``maximal munch rule''): The 

longest initial substring matched by any regular expression is taken

as next token.\bigskip

\item Rule priority:

For a particular longest initial substring, the first regular

expression that can match determines the token.

\end{itemize}

%\url{http://www.technologyreview.com/tr10/?year=2011}

%finite deterministic automata/ nondeterministic automaton

%\item problem with infix operations, for example i-12

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

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

\begin{frame}[c]

\begin{itemize}

\item Regular expression for email addresses

\begin{center}

\begin{tabular}{l}

(name: \bl{$[a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+$})\bl{$\cdot @\cdot$}\\ 

\qquad(domain: \bl{$[a\mbox{-}z0\mbox{-}9\,.-]^+$}) \bl{$\cdot .\cdot$}\\ 

\qquad\qquad(top\_level: \bl{$[a\mbox{-}z\,.]^{\{2,6\}}$})

\end{tabular}

\end{center}

\bl{\[

\texttt{christian.urban@kcl.ac.uk}

\]}

\item result environment:

\begin{center}

\begin{tabular}{l}

\bl{$[(name:\texttt{christian.urban}),$}\\ 

\bl{$\phantom{[}(domain:\texttt{kcl}),$}\\ 

\bl{$\phantom{[}(top\_level:\texttt{ac.uk})]$}

\end{tabular}

\end{center}

\end{itemize}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Coursework}

\begin{center}

\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}

\bl{$nullable([c_1 c_2 \ldots c_n])$}  & \bl{$\dn$} & $?$\\

\bl{$nullable(r^+)$}                   & \bl{$\dn$} & $?$\\

\bl{$nullable(r^?)$}                   & \bl{$\dn$} & $?$\\

\bl{$nullable(r^{\{n,m\}})$}            & \bl{$\dn$} & $?$\\

\bl{$nullable(\sim{}r)$}               & \bl{$\dn$} & $?$\medskip\\

\bl{$der\, c\, ([c_1 c_2 \ldots c_n])$}  & \bl{$\dn$} & $?$\\

\bl{$der\, c\, (r^+)$}                   & \bl{$\dn$} & $?$\\

\bl{$der\, c\, (r^?)$}                   & \bl{$\dn$} & $?$\\

\bl{$der\, c\, (r^{\{n,m\}})$}            & \bl{$\dn$} & $?$\\

\bl{$der\, c\, (\sim{}r)$}               & \bl{$\dn$} & $?$\\

\end{tabular}

\end{center}

\end{frame}

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