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

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

\begin{document}

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

\begin{frame}[t]

\frametitle{%

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

  \\[-3mm]

  \LARGE Compilers and \\[-2mm] 

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

  \end{tabular}}

  \normalsize

  \begin{center}

  \begin{tabular}{ll}

  \end{tabular}

  \end{center}

\end{frame}

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

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

\begin{frame}[c]

\begin{center}

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

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

  \only<-7>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};}

  \only<8->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};}                           

  \only<-7>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};}

  \only<8->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};}

  \node[state] (q2) at ( 2,1) {$\mbox{Q}_2$};

  \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)

                  (q1) edge[bend left] node[above] {\alert{$b$}} (q0)

                  (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)

                  (q1) edge node[above] {\alert{$a$}} (q2)

                  (q2) edge [loop right] node {\alert{$a$}} ()

                  (q0) edge [loop below] node {\alert{$b$}} ()

            ;

\end{tikzpicture}

\end{center}\bigskip

\begin{center}

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

\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b +  \mbox{Q}_2\,b$}\\

\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\

\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\

\end{tabular}

\end{center}

Arden's Lemma:

\begin{center}

If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}

\end{center}

\only<2-6>{\small

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

\begin{bubble}[6.7cm]

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

\multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} \& \bl{$\mbox{Q}_2$}:}\\    

\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b +  \mbox{Q}_2\,b$}\\

\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}

\end{tabular}

\end{bubble}

\end{textblock}}

\only<3-6>{\small

\begin{textblock}{6}(2,4.15)

\begin{bubble}[6.7cm]

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

\multicolumn{3}{@{}l}{simplifying \bl{$\mbox{Q}_0$}:}\\    

\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\

\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}

\end{tabular}

\end{bubble}

\end{textblock}}

\only<4-6>{\small

\begin{textblock}{6}(3,7.55)

\begin{bubble}[6.7cm]

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

  \multicolumn{3}{@{}l}{Arden for \bl{$\mbox{Q}_2$}:}\\    

\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\

\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$}

\end{tabular}

\end{bubble}

\end{textblock}}

\only<5-6>{\small

\begin{textblock}{6}(4,10.9)

\begin{bubble}[7.5cm]

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

  \multicolumn{3}{@{}l}{Substitute \bl{$\mbox{Q}_2$} and simplify:}\\    

\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b)$}\\

\end{tabular}

\end{bubble}

\end{textblock}}

\only<6>{\small

\begin{textblock}{6}(5,13.4)

\begin{bubble}[7.5cm]

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

  \multicolumn{3}{@{}l}{Arden again for \bl{$\mbox{Q}_0$}:}\\    

\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\

\end{tabular}

\end{bubble}

\end{textblock}}

\only<7->{\small

\begin{textblock}{6}(6,11.5)

\begin{bubble}[6.7cm]

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

\multicolumn{3}{@{}l}{Finally:}\\    

\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\

\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a$}\\

\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a^*)$}\\

\end{tabular}

\end{bubble}

\end{textblock}}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Regexps and Automata}

\begin{center}

\begin{tikzpicture}

\node (rexp)  {\bl{\bf Regexps}};

\node (nfa) [right=of rexp] {\bl{\bf NFAs}};

\node (dfa) [right=of nfa] {\bl{\bf DFAs}};

\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}};

\path[->,red, line width=2mm] (rexp) edge node [above=4mm, black] 

     {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa);

\path[->,red, line width=2mm] (nfa) edge node [above=4mm, black] 

     {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa);

\path[->, red, line width=2mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa);

%%\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp);

\path[->, red, line width=2mm] (dfa) edge [bend left=45] node [below, black] {\begin{tabular}{l}Brzozowski's\\ method\end{tabular}} (rexp);

\end{tikzpicture}\\

\end{center}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}}

\begin{tikzpicture}

\begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs},

    enlargelimits=false,

    xtick={0,5,...,30},

    xmax=30,

    ymax=35,

    ytick={0,5,...,30},

    scaled ticks=false,

    axis lines=left,

    width=10cm,

    height=7cm, 

    legend entries={Python,Ruby,my NFA},  

    legend pos=north west,

    legend cell align=left]

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

\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data};  

\addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data};	 

\end{axis}

\end{tikzpicture}

The punchline is that many existing libraries do depth-first search

in NFAs (backtracking).

\end{frame}

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

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

% \begin{frame}[c]

% \frametitle{DFA to Rexp}

% \begin{center}

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

%                     every state/.style={minimum size=0pt,

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

%   \node[state, initial]        (q0) at ( 0,1) {$q_0$};

%   \node[state]                    (q1) at ( 1,1) {$q_1$};

%   \node[state, accepting] (q2) at ( 2,1) {$q_2$};

%   \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)

%             (q1) edge[bend left] node[above] {\alert{$b$}} (q0)

%             (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)

%             (q1) edge node[above] {\alert{$a$}} (q2)

%             (q2) edge [loop right] node {\alert{$a$}} ()

%             (q0) edge [loop below] node {\alert{$b$}} ();

% \end{tikzpicture}

% \end{center}\bigskip

% \begin{center}

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

% \bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b +  q_2\,b$} & (start state)\\

% \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\

% \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\

% \end{tabular}

% \end{center}

% Arden's Lemma:

% \begin{center}

% If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}

% \end{center}

% \end{frame}

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

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

% \begin{frame}[c]

% \frametitle{DFA Minimisation}

% \begin{enumerate}

% \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$}

% \item Mark all pairs that accepting and non-accepting states

% \item For  all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether

% \begin{center}

% \bl{$(\delta(q, c), \delta(p,c))$}

% \end{center} 

% are marked. If yes, then also mark \bl{$(q, p)$}.

% \item Repeat last step until no change.

% \item All unmarked pairs can be merged.

% \end{enumerate}

% \end{frame}

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

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

% \begin{frame}[c]

% \begin{center}

% \begin{tabular}{@{\hspace{-8mm}}cc@{}}

% \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)  {$q_0$};

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

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

% \node[state] (q_3) [right=of q_2] {$q_3$};

% \node[state, accepting] (q_4) [right=of q_1] {$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}

% &

% \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm]

% \draw (0,0) -- (4,0);

% \draw (0,1) -- (4,1);

% \draw (0,2) -- (3,2);

% \draw (0,3) -- (2,3);

% \draw (0,4) -- (1,4);

% \draw (0,0) -- (0, 4);

% \draw (1,0) -- (1, 4);

% \draw (2,0) -- (2, 3);

% \draw (3,0) -- (3, 2);

% \draw (4,0) -- (4, 1);

% \draw (0.5,-0.5) node {$q_0$}; 

% \draw (1.5,-0.5) node {$q_1$}; 

% \draw (2.5,-0.5) node {$q_2$}; 

% \draw (3.5,-0.5) node {$q_3$};

% \draw (-0.5, 3.5) node {$q_1$}; 

% \draw (-0.5, 2.5) node {$q_2$}; 

% \draw (-0.5, 1.5) node {$q_3$}; 

% \draw (-0.5, 0.5) node {$q_4$}; 

% \draw (0.5,0.5) node {\large$\star$}; 

% \draw (1.5,0.5) node {\large$\star$}; 

% \draw (2.5,0.5) node {\large$\star$}; 

% \draw (3.5,0.5) node {\large$\star$};

% \draw (0.5,1.5) node {\large$\star$}; 

% \draw (2.5,1.5) node {\large$\star$}; 

% \draw (0.5,3.5) node {\large$\star$}; 

% \draw (1.5,2.5) node {\large$\star$}; 

% \end{tikzpicture}}

% \end{tabular}

% \end{center}

% \mbox{}\\[-20mm]\mbox{}

% \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_02)  {$q_{0, 2}$};

% \node[state] (q_13) [right=of q_02] {$q_{1, 3}$};

% \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$};

% \path[->] (q_02) edge [bend left] node [above]  {\alert{$a$}} (q_13);

% \path[->] (q_13) edge [bend left] node [below]  {\alert{$b$}} (q_02);

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

% \path[->] (q_13) edge node [above]  {\alert{$a$}} (q_4);

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

% \end{tikzpicture}\\

% minimal automaton

% \end{center}

% \end{frame}

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

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

\begin{frame}[c]

\frametitle{Regular Languages}

Two equivalent definitions:\bigskip

\begin{quote}\rm A language is \alert{regular} iff there exists a

regular expression that recognises all its strings.

\end{quote}

\begin{quote}\rm A language is \alert{regular} iff there exists an

automaton that recognises all its strings.

\end{quote}\bigskip\bigskip

\small

for example \bl{$a^nb^n$} is not regular

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Negation}

Regular languages are closed under negation:\bigskip

\begin{center}

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

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

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

  \only<1>{\node[state,initial] (q0) at ( 0,1) {$q_0$};}

  \only<2>{\node[state,initial,accepting] (q0) at ( 0,1) {$q_0$};}

  \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};}

  \only<2>{\node[state,accepting] (q1) at ( 1,1) {$q_1$};}

  \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};}

  \only<2>{\node[state] (q2) at ( 2,1) {$q_2$};}

  \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)

            (q1) edge[bend left] node[above] {\alert{$b$}} (q0)

            (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)

            (q1) edge node[above] {\alert{$a$}} (q2)

            (q2) edge [loop right] node {\alert{$a$}} ()

            (q0) edge [loop below] node {\alert{$b$}} ();

\end{tikzpicture}

\end{center}\bigskip\bigskip

But requires that the automaton is \alert{completed}!

\end{frame}

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

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

\begin{frame}[c]

\frametitle{The Goal of this Course}

\mbox{}\\[-26mm]\mbox{}

\begin{center}

  \begin{tikzpicture}[scale=1,

                      node/.style={

                      rectangle,rounded corners=3mm,

                      very thick,draw=black!50,

                      minimum height=18mm, minimum width=20mm,

                      top color=white,bottom color=black!20}]

  \node at (3.05, 1.8) {\Large\bf Write a compiler};

  \node (0) at (-2.3,0) {}; 

  \node (A) at (0,0)  [node] {};

  \node [below right] at (A.north west) {lexer};

  \node (B) at (3,0)  [node] {};

  \node [below right=1mm] at (B.north west) 

    {\mbox{}\hspace{-1mm}parser};

  \node (C) at (6,0)  [node] {};

  \node [below right] at (C.north west) 

    {\mbox{}\hspace{-1mm}code gen};

  \node (1) at (8.4,0) {}; 

  \draw [->,line width=4mm] (0) -- (A); 

  \draw [->,line width=4mm] (A) -- (B); 

  \draw [->,line width=4mm] (B) -- (C); 

  \draw [->,line width=4mm] (C) -- (1); 

  \end{tikzpicture}

  \end{center}

Today a lexer.  

\only<2>{

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

\begin{tabular}{c}

\includegraphics[scale=0.13]{../pics/rosetta.jpg}\\[-2mm]

\footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta)

\end{tabular}

\end{textblock}}

\end{frame}

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

\begin{frame}[c]

\frametitle{Regular Expressions}

In programming languages they are often used to recognise:\medskip

\begin{itemize}

\item symbols, digits

\item identifiers

\item numbers (non-leading zeros)

\item keywords

\item comments

\end{itemize}\bigskip

\mbox{}\hfill\bl{\url{http://www.regexper.com}}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Lexing: Test Case}

\mbox{\lstinputlisting[language=While]{../progs/fib.while}}

\end{frame}

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

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

%\begin{frame}[c]

%\frametitle{?? Test Case}

%

%\mbox{\lstinputlisting[language=While]{../progs/collatz.while}}

%

%\end{frame}

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

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

\begin{frame}[t]

\tt

\begin{center}\large

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

\end{center}

\begin{tabular}{@{}l}

KEYWORD: \\

\hspace{5mm}{if}, {then}, {else},\\ 

WHITESPACE:\\

\hspace{5mm}{" "}, {$\backslash$n},\\ 

IDENTIFIER:\\

\hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + {\_})$^*$\\ 

NUM:\\

\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {0}\\