% !TEX program = xelatex

\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}

\usepackage{../slides}

\usepackage{../graphicss}

\usepackage{../langs}

\usepackage{../data}

\usepackage{tcolorbox}

\newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black}

\newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1}

\newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1}

\hfuzz=220pt 

\pgfplotsset{compat=1.17}

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

% beamer stuff 

\renewcommand{\slidecaption}{CFL 03, King's College London}

\begin{document}

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

\begin{frame}[t]

\frametitle{%

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

  \\[-3mm]

  \LARGE Compilers and \\[-1mm] 

  \LARGE Formal Languages\\[-5mm] 

  \end{tabular}}

  \normalsize

  \begin{center}

  \begin{tabular}{ll}

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

    Office Hour: & Friday 12 -- 14\\  

  Location: & N7.07 (North Wing, Bush House)\\

  Slides \& Progs: & KEATS\\

  Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\  

  \end{tabular}

  \end{center}

  \begin{center}

    \begin{tikzpicture}

      \node[drop shadow,fill=white,inner sep=0pt] 

      {\footnotesize\rowcolors{1}{capri!10}{white}

        \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline

          1 Introduction, Languages          & 6 While-Language \\

          2 Regular Expressions, Derivatives & 7 Compilation, JVM \\

          \cellcolor{blue!50}

          3 Automata, Regular Languages      & 8 Compiling Functional Languages \\

          4 Lexing, Tokenising               & 9 Optimisations \\

          5 Grammars, Parsing                & 10 LLVM \\ \hline

        \end{tabular}%

      };

    \end{tikzpicture}

  \end{center}

\end{frame}

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

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

{

\setbeamercolor{background canvas}{bg=cream}

\begin{frame}[c]

\frametitle{For Installation Problems}

\begin{itemize}

\item Harry Dilnot (harry.dilnot@kcl.ac.uk) \\

  \;\;Windows expert

\item Oliver Iliffe (oliver.iliffe@kcl.ac.uk) 

\end{itemize}

\end{frame}

}

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

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

\begin{frame}[c]

\begin{mybox3}{From Pollev last week}\it    

Is the equivalence of two regexes belong in the P or NP class of problems?

\end{mybox3}  

\end{frame}

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

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

\begin{frame}[c]

\begin{mybox3}{From Pollev last week}\it    

  If state machines are not efficient, then how/why do many lexer

  packages like the logos crate in rust compile down a lexer

  definition down to a jump table driven state machine?

  \textcolor{gray}{Could we

  achieve quicker lexing with things like SIMD instructions?}

\end{mybox3}  

\end{frame}

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

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

\begin{frame}[c]

\frametitle{\boldmath$(abcdef)^{\{n\}}$ in Rust and Scala}

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

\begin{tikzpicture}

\begin{axis}[

    xlabel={copies of $[abcdef]$}, 

    x label style={at={(0.45,-0.16)}},

    ylabel={time in secs},

    enlargelimits=false, 

    ytick={0,10,...,60},

    ymax=65,

    xmax=50000,

    xtick={0,10000,...,40000},

    scaled ticks=false,

    axis lines=left,

    width=10cm,

    height=6cm,

    legend entries={Rust, Scala V3},

    legend style={font=\small,at={(1.15,0.48)},anchor=north},

    legend cell align=left]

    \addplot[blue,mark=*, mark options={fill=white}] table {re-rust2.data};

    \only<2>{\addplot[red,mark=*, mark options={fill=white}] table {re-scala2.data};}

\end{axis}

\end{tikzpicture}

\end{textblock}

\end{frame}

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

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

\begin{frame}[c]

\begin{mybox3}{From Pollev last week}\it    

  For a regular expression $r = r_1 \cdot r_2$, to prove that

  $der\;c\;r = (der\;c\;r) \cdot r^{\{n-1\}}$, is there a

  way to prove it in the general case instead

  of how you do the calculations for each $n$ in the videos?

\end{mybox3}  

\end{frame}

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

{

\setbeamercolor{background canvas}{bg=cream}

\begin{frame}<1-10>[c]

\end{frame}

}

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

%\begin{frame}[c]

%\frametitle{Scala Book, Exams}

%

%\begin{itemize}

%\item \small https://nms.kcl.ac.uk/christian.urban/ProgInScala2ed.pdf\normalsize

%\item homework (written exam 80\%)

%\item coursework (20\%)\bigskip

%\item short survey at KEATS; to be answered until Sunday    

%\end{itemize}

%\end{frame}

%%%%%%%%%%%

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

\begin{frame}[t]

\frametitle{(Basic) Regular Expressions}

\begin{center}

   \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}

  \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}  & nothing\\

         & \bl{$\mid$} & \bl{$\ONE$}        & 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{center}

How about ranges \bl{$[a\mbox{-}z]$}, \bl{$r^+$} and \bl{$\sim{}r$}? Do they increase the

set of languages we can recognise?

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Negation}

Assume you have an alphabet consisting of the letters \bl{$a$}, \bl{$b$} and \bl{$c$} only.

Find a (basic!) regular expression that matches all strings \emph{\alert{except}} 

\bl{$ab$} and \bl{$ac$}!

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Automata}

A \alert{\bf deterministic finite automaton}, DFA, consists of:

\begin{itemize}

\item an alphabet \bl{$\varSigma$}  

\item a set of states \bl{$\mbox{Qs}$}

\item one of these states is the start state \bl{$\mbox{Q}_0$}

\item some states are accepting states \bl{$F$}, and

\item there is transition function \bl{$\delta$}\bigskip 

\small

which takes a state as argument and a character and produces a 

new state; this function might not be everywhere defined $\Rightarrow$ partial function

\end{itemize}

\begin{center}

\bl{$A(\varSigma, \mbox{Qs}, \mbox{Q}_0, F, \delta)$}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\begin{center}

\begin{tikzpicture}[>=stealth',very thick,auto,

  every state/.style={minimum size=0pt,inner sep=2pt,

    draw=blue!50,very thick,fill=blue!20},]

\node[state,initial]  (Q_0)  {$\mbox{Q}_0$};

\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};

\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};

\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};

\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};

\path[->] (Q_0) edge node [above]  {\alert{$a$}} (Q_1);

\path[->] (Q_1) edge node [above]  {\alert{$a$}} (Q_4);

\path[->] (Q_4) edge [loop right] node  {\alert{$a, b$}} ();

\path[->] (Q_3) edge node [right]  {\alert{$a$}} (Q_4);

\path[->] (Q_2) edge node [above]  {\alert{$a$}} (Q_3);

\path[->] (Q_1) edge node [right]  {\alert{$b$}} (Q_2);

\path[->] (Q_0) edge node [above]  {\alert{$b$}} (Q_2);

\path[->] (Q_2) edge [loop left] node  {\alert{$b$}} ();

\path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (Q_0);

\end{tikzpicture}

\end{center}

\mbox{}\\[-14mm]

\only<1>{

\begin{itemize}

\item the start state can be an accepting state

\item it is possible that there is no accepting state

\item all states might be accepting (but this does not necessarily mean all strings are accepted)

\end{itemize}}

\only<2>{

for this automaton \bl{$\delta$} is the function\\

\begin{center}

\begin{tabular}{lll}

  \bl{$(\mbox{Q}_0, a) \rightarrow \mbox{Q}_1$} & \bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_4$}

  & \bl{$(\mbox{Q}_4, a) \rightarrow \mbox{Q}_4$}\\

  \bl{$(\mbox{Q}_0, b) \rightarrow \mbox{Q}_2$} & \bl{$(\mbox{Q}_1, b) \rightarrow \mbox{Q}_2$} &

  \bl{$(\mbox{Q}_4, b) \rightarrow \mbox{Q}_4$}\\

\end{tabular}\ldots

\end{center}  

}  

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Accepting a String}

Given

\begin{center}

\bl{$A(\varSigma, \mbox{Qs}, \mbox{Q}_0, F, \delta)$}

\end{center}

you can define

\begin{center}

\begin{tabular}{l}

\bl{$\widehat{\delta}(Q, []) \dn Q$}\\

\bl{$\widehat{\delta}(Q, c::s) \dn \widehat{\delta}(\delta(Q, c), s)$}\\

\end{tabular}

\end{center}\pause

Whether a string \bl{$s$} is accepted by \bl{$A$}?

\begin{center}

\hspace{5mm}\bl{$\widehat{\delta}(\mbox{Q}_0, s) \in F$}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Regular Languages}

A \alert{\bf language} is a set of strings.\bigskip

A \alert{\bf regular expression} specifies a language.\bigskip

A language is \alert{\bf regular} iff there exists

a regular expression that recognises all its strings.\bigskip\bigskip\pause

not all languages are regular, e.g.~\bl{$a^nb^n$} is not

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Regular Languages (2)}

A language is \alert{\bf regular} iff there exists a regular

expression that recognises all its strings.\bigskip\medskip

or {\bf equivalently}\bigskip\medskip

A language is \alert{\bf regular} iff there exists a

deterministic finite automaton that recognises all its

strings.

\end{frame}

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

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

\begin{frame}[c]

\frametitle{\begin{tabular}{c}

              Non-Deterministic\\[-1mm] 

              Finite Automata\end{tabular}}

\bl{$N(\varSigma, \mbox{Qs}, \mbox{Qs}_0, F, \rho)$}\\

A non-deterministic finite automaton (NFA) consists of:

\begin{itemize}

\item a finite set of states, \bl{$Qs$}

\item \underline{some} these states are the start states, \bl{$Qs_0$}

\item some states are accepting states, and

\item there is transition \alert{relation}, \bl{$\rho$}\medskip 

\end{itemize}

\begin{center}

\begin{tabular}{c}

\bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_2$}\\

\bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_3$}\\

\end{tabular}

\bl{\ldots}

\hspace{10mm}\pause

\bl{$(\mbox{Q}_1, a) \rightarrow \{\mbox{Q}_2, \mbox{Q}_3\}$}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{An NFA Example}

% A NFA for (ab* + b)*a

\begin{center}

\begin{tikzpicture}[>=stealth',very thick, auto,

    every state/.style={minimum size=0pt,inner sep=3pt,

      draw=blue!50,very thick,fill=blue!20},scale=2]

\node[state,initial]  (Q_0)  {$\mbox{Q}_0$};

\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};

\node[state, accepting] (Q_2) [right=of Q_1] {$\mbox{Q}_2$};

\path[->] (Q_0) edge [loop above] node  {\alert{$b$}} ();

\path[<-] (Q_0) edge node [below]  {\alert{$b$}} (Q_1);

\path[->] (Q_0) edge [bend left] node [above]  {\alert{$a$}} (Q_1);

\path[->] (Q_0) edge [bend right] node [below]  {\alert{$a$}} (Q_2);

\path[->] (Q_1) edge [loop above] node  {\alert{$a,b$}} ();

\path[->] (Q_1) edge node  [above] {\alert{$a$}} (Q_2);

\end{tikzpicture}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Another Example}

For the regular expression \bl{$(.^*)a\,(.^{\{n\}})bc$}\bigskip\bigskip

% \begin{center}

\mbox{}\hspace{-11.5mm}

	\begin{tikzpicture}[>=stealth',very thick, auto,

	every state/.style={minimum size=5pt,inner sep=1pt,

		draw=blue!50,very thick,fill=blue!20},scale=1, node distance=5mm,

	decoration={brace,mirror,amplitude=7}]

	\node[state,initial]  (Q_0)  {$\;0\;$};

	\node[state] (Q_1) [right=of Q_0] {$\;1\;$};

	\node[state] (Q_2) [right=of Q_1] {$\;2\;$};

	\node (Q_3) [right=of Q_2] {$\hspace{-1mm}\ldots\hspace{-3mm}$};

	\node[state] (Q_4) [right=of Q_3] {$\;\phantom{1}\;$};

	\node (Q_5) [right=of Q_4] {$\hspace{-1mm}\ldots\hspace{-3mm}$};

	\node[state] (Q_6) [right=of Q_5] {\tiny$n+1$};

	\node[state] (Q_7) [right=of Q_6] {\tiny$n+2$};

	\node[state,accepting] (Q_8) [right=of Q_7] {\tiny$n+3$};

	\path[->] (Q_0) edge [loop above] node {$*$} ();

	\path[->] (Q_0) edge node [above] {$a$} (Q_1);

	\path[->] (Q_1) edge node [above] {$*$} (Q_2);

	\path[->] (Q_2) edge node [above] {$*$} (Q_3);

	\path[->] (Q_4) edge node [above] {$*$} (Q_5);

	\path[->] (Q_5) edge node [above] {$*$} (Q_6);

	\path[->] (Q_6) edge node [above] {$b$} (Q_7);

	\path[->] (Q_7) edge node [above] {$c$} (Q_8);

	\draw [decorate] ([yshift=-5mm]Q_1.east) --node[below=3mm]{$n$} ([yshift=-5mm]Q_6.west);

	\end{tikzpicture}\bigskip

{\small Note the star-transitions: accept any character.}

\end{frame}

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

\begin{frame}[c]

\frametitle{Two Epsilon NFA Examples}

\small

\begin{center}

\begin{tabular}[t]{c@{\hspace{9mm}}c}

\begin{tikzpicture}[scale=0.7,>=stealth',very thick,

                             every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]

\node[state,initial]  (q_0)  {$q_0$};

\node[state] (q_1) [above=of q_0] {$q_1$};

\node[state, accepting] (q_2) [below=of q_0] {$q_2$};

\path[->] (q_0) edge node [left]  {\alert{$\epsilon$}} (q_1);

\path[->] (q_0) edge node [left]  {\alert{$\epsilon$}} (q_2);

\path[->] (q_0) edge [loop right] node  {\alert{$a$}} ();

\path[->] (q_1) edge [loop above] node  {\alert{$a$}} ();

\path[->] (q_2) edge [loop below] node  {\alert{$b$}} ();

\end{tikzpicture} &

\raisebox{20mm}{

\begin{tikzpicture}[scale=0.7,>=stealth',very thick,

                             every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]

\node[state,initial]  (r_1)  {$r_1$};

\node[state] (r_2) [above=of r_1] {$r_2$};

\node[state, accepting] (r_3) [right=of r_1] {$r_3$};

\path[->] (r_1) edge node [below]  {\alert{$b$}} (r_3);

\path[->] (r_2) edge [bend left] node [above]  {\alert{$a$}} (r_3);

\path[->] (r_1) edge [bend left] node  [left] {\alert{$\epsilon$}} (r_2);

\path[->] (r_2) edge [bend left] node  [right] {\alert{$a$}} (r_1);

\end{tikzpicture}}

\end{tabular}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Thompson: Rexp to $\epsilon$NFA}

\begin{center}

\begin{tabular}[t]{l@{\hspace{10mm}}l}

\raisebox{1mm}{\bl{$\ZERO$}} & 

\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

\node[state, initial]  (Q_0)  {$\mbox{}$};

\end{tikzpicture}\\\\

\raisebox{1mm}{\bl{$\ONE$}} & 

\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

\node[state, initial, accepting]  (Q_0)  {$\mbox{}$};

\end{tikzpicture}\\\\

\raisebox{5mm}{\bl{$c$}} & 

\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

\node[state, initial]  (Q_0)  {$\mbox{}$};