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

\usepackage{../slides}

\usepackage{../graphics}

\usepackage{../langs}

\usepackage{../data}

\usepackage{../grammar}

\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]

\frametitle{\begin{tabular}{c}Last Week\\[-1mm] 

            Regexes and Values\end{tabular}}

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

$\mapsto$

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Records}

\begin{itemize}

\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: 

\bl{$Rec(x,v)$}\medskip

\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)$}

\end{itemize}\bigskip\bigskip

\small

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

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Environments}

Obtaining the ``recorded'' parts of a value: 

\begin{center}

\begin{tabular}{lcl}

  \bl{$env(Empty)$}     & \bl{$\dn$} & \bl{$[]$}\\

  \bl{$env(Char(c))$}   & \bl{$\dn$} & \bl{$[]$}\\

  \bl{$env(Left(v))$}   & \bl{$\dn$} & \bl{$env(v)$}\\

  \bl{$env(Right(v))$}  & \bl{$\dn$} & \bl{$env(v)$}\\

  \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\

  \bl{$env([v_1,\ldots ,v_n])$} & \bl{$\dn$} & 

     \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\

  \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\

\end{tabular}

\end{center}

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

\code{"if true then then 42 else +"}

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

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Two Rules}

\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

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

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

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

\begin{frame}[c]

\frametitle{Regular Languages}

While regular expressions are very useful for lexing, there is

no regular expression that can recognise the language

\bl{$a^nb^n$}.\bigskip

\begin{center}

\bl{$(((()()))())$} \;\;vs.\;\; \bl{$(((()()))()))$}

\end{center}\bigskip\bigskip

\small

\noindent So we cannot find out with regular expressions

whether parentheses are matched or unmatched. Also regular

expressions are not recursive, e.g.~\bl{$(1 + 2) + 3$}.

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Hierarchy of Languages}

\begin{center}

\begin{tikzpicture}

[rect/.style={draw=black!50, 

              top color=white,

              bottom color=black!20, 

              rectangle, 

              very thick, 

              rounded corners}, scale=1.2]

\draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};

\draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};

\draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};

\draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};

\draw (0,-1.4) node [rect] {regular languages};

\end{tikzpicture}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{CF Grammars}

A \alert{\bf context-free grammar} \bl{$G$} consists of

\begin{itemize}

\item a finite set of nonterminal symbols (upper case)

\item a finite terminal symbols or tokens (lower case)

\item a start symbol (which must be a nonterminal)

\item a set of rules

\begin{center}

\bl{$A \rightarrow \textit{rhs}$}

\end{center}

where \bl{\textit{rhs}} are sequences involving terminals and nonterminals,

including the empty sequence \bl{$\epsilon$}.\medskip\pause

We also allow rules

\begin{center}

\bl{$A \rightarrow \textit{rhs}_1 | \textit{rhs}_2 | \ldots$}

\end{center}

\end{itemize}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Palindromes}

A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:

\begin{center}

\bl{\begin{tabular}{lcl}

$S$ & $\rightarrow$ &  $\epsilon$ \\

$S$ & $\rightarrow$ &  $a\cdot S\cdot a$ \\

$S$ & $\rightarrow$ &  $b\cdot S\cdot b$ \\

\end{tabular}}

\end{center}\pause

or

\begin{center}

\bl{\begin{tabular}{lcl}